Hi,
After I upgraded my ZCS from 6.x version to 7.x few months ago, I faced the exact the same problem on not many, but few Outlook clients. Beside that, ZCS 7.x works fine, no problems.
Here is is from my Outlook 2010:
Code:
Your server reported a UID that does not comply with the IMAP
standard. This typically indicates a server bug. Your program may
not function properly after this.
DETAILS:
MsgSeqNum 35, New UID 40353. Prev UID: 40353, Next UID: 40355.
Protocol: IMAP
Server: zimbra.server.com
Port: 143
Error Code: 0x800CCCDC
As one of the problematic Outlooks is also my own machine, I tried all these to solve the problem:
- deleted IMAP account in Outlook, but no help
- removed also IMAP.PST store on computer, and recreated new one, but no help
- remove whole Office 2010, deleted all remaining folders, recreated Outlook profile, account....THIS HELPED
...but only for 1 month. Now again I've got this error.

- Now I changed IMAP port from SSL 993 to TLS 143, but still no help.
Anybody having such a problems?
I mean -
might it be ZCS server related?
---- EDITED WITH QUICK INFO ----
For all of you, who are having the same problems, here I edited the initial post with key information from the whole thread.
FIRST, Bug has been reported for this issue:
https://bugzilla.zimbra.com/show_bug.cgi?id=62160
Please vote, if you have the same problem!
SECOND, maybe what you want, possible temporary workaround, which might help in most cases:
AFAIK, problem is in most cases with one of the mail items in "Trash" or "Drafts". So it might help if you delete those mails in both, webmail and Outlook.