Sorry for my bad english. I try to explain it more detailed.
The Problem is defenitivly Outlook 2010. And it happens only if you are using the target IMAP Account with more than one Machine.
The deleting process in Outlook 2010 IMAP (Standard Settings) works like the deleting Process in POP3 (Local Database). (Out of the view of the User)
By default you dont see "Marked to Delete Emails" in the imap Account. You hit the delete button and Outlook copies the message into trash and Mark the Original message to delete. You dont see the marked original message because they is hidden. You could see them, if you enable the IMAP View.
Now you switch into another Folder. When you Switch back the marked Messages will be deleted permanent.
And exactly this causes the UID Problem.
But only if you use more than one machine with the same IMAP Account.
The UID Failure does not appear on the Machine which deleted the Message, but on every other Machine using this IMAP Account.
The Workaround is simple. Disable "Move deleted items to the following Folder" and the UID Error does not appear any more.
In the best case you disable "Purge items when switching Folder" and Enable the IMAP View under View Settings.
Then Outlook 2010 works like Outlook 2007 and older.
I hope you understand now what i mean and you can track the Problem.
Many Greetz from Germany