We found and fixed the issue. As Mike says, it appears to only have affected Outlook 2007 and IMAP users. EWS/EAS accounts didn't see the issue.
The problem stemmed from some changes made to how IMAP "marked as deleted" translated to EWS, specifically in eM Client. Other clients using EWS -- like Apple Mail -- actually removed the message when deleted in IMAP, but eM Client didn't. So, a change was made to force that same behavior in eM Client. This is what caused the UID issue for those users, and this is what was rolled back.
We'll be pushing a new build to the public this week that contains this fix. If you want a pre-release build rather than wait for the minor, feel free to PM me or send a ticket to our Sales Team and we'll hook you up.