We recently switched to Office 365. All of our iPhone users are now complaining of random occurrences of the following:
1. Receive an email. Can read it ok.
2. Wait several days (to allow the message to not be cached on the iPhone)
3. "Search" for that email on the iPhone
4. When the email is found, the following error is reported: "This message has not been downloaded from the server"
5. Appears to random.
6. At least two of the emails with this error had attachments to them.
7. Many of these emails are quite small.
8. Not seeing this problem on Android or Windows phones.