I had a similar problem with Outlook 2003 and it turn out to be an issue with the Outlook preview pane. If the message was displayed in the preview pane while it was being restored I got the error messages that you are describing. I fix the problem by changing the policies - Desktop - Fix Outlook Preview Pane - to Apply Automatically and it fixed the problem (then re-sync all mailboxes). The desktop property item reads as if it is specific to Outlook XP but there must a problem with using EV with the Outlook Preview Pane in general.
Thanks for your help, we have finally narrowed it down to a bespoke COM addin, it seems it was a mixture of the COM addin and an Outlook XP hotfix, we modified the addin and the issue is resolved.