[Update - I switched to IMAP instead of POP for connecting to my email server and it seems much better.  It also marks messages as "read" on the phone once I read them on my computer, which was a previously major annoyance.  I would recommend IMAP if it's available to you.]

I have my iPhone set to retrieve email messages from my POP3 account. This works great except that about every 10th message would show “This message has not been downloaded from the server” instead of the message text.

I discovered that this was not actually a problem with the iPhone, rather with my email setup. I also have Outlook on my desktop which is configured to remove messages from the server after downloading. What happens is that the iPhone downloads the headers but does not get the full message body until you actually read the message. Meanwhile, Outlook downloads all new messages and immediately removes them from the server. So when you try to read an email on the iPhone for the first time, it only has the headers and needs to retrieve the message body from the server. However if Outlook was opened then it probably removed the messages from the server. So there is no way for the iPhone to get the message body. It would make more sense if the error message on the iPhone was changed to “This message is no longer available on the server.”

There is a fairly simple work-around to this problem. Just configure your desktop email client so it doesn’t immediately remove messages after downloading. In my case using Outlook, there is a setting to leave mail on the server for X days (I set mine to 3 days). This resolved the issue for me entirely, however if I try to read an email on the iPhone that is more than 3 days old it won’t be available. Basically the number of days you configure your client to retain messages on the server is how far back they will be available via your iPhone. For me 3 days is plenty. However, if you want to have access to older messages you can set the retention to 30 days or whatever your email client and host will allow.