Once in a while I am unable to delete an email message on my iPhone. It throws an "unable to move message to trash" error message. I use the normal iPhone Mail app and have an MS Exchange mailbox that syncs with my office email.
While this problem was well-documented for IMAP mailboxes, I could not find a solution for MS Exchange mailboxes.
Turn off the mail sync, then turn it back on.
* Mail, Contact, Calendars
* Touch your Exchange email account. You'll see a list of the things it syncs (e.g. Mail, Contacts, Calendars, etc.).
* Turn off the mail sync.
* Open the Mail app to confirm that your Exchange mailbox is no longer there.
* Return to the settings and switch the mail sync back on. Your mail will be re-synchronized with the Exchange server and the troublesome messages will disappear.