I have a similar problem. Some messages download completely. Others come in with a headline and a statement that, "This message has not been downloaded from the server.
Is this email account a POP account and if so, are you also accessing the account with an email client on your computer that is launched and actively checking the account for new messages at the same time as your iPhone?
If so, this error message is due to the incoming mail server for the account temporarily locking the account's Inbox mailbox. Although a POP account can be accessed with multiple email clients, it is primarily designed to be accessed with a single email client only. Multiple email clients cannot check the incoming mail server for a POP account at or near the same time. This error message usually indicates this has occurred.