Had some problems on an Exchange server with deleting some special messages. The email was shown like all others but it was not able to delete the email. After some research and testing it finally worked by enabling the Cache-Mode in one Outlook client connected to the mailbox synchronizing it and deleting the message.
Maybe this short description help someone with the same problem. You can contact me if you need more information but because it is a customers server and environment I will not provide more information about configuration or screenshots.