[Dovecot] Why do these keep showing up?

2010-10-08 14:37:29 imap hmarie@olypen.com: Error: Mailbox Removed: Expunged GUID mismatch for UID 1257: ceb413227b55e8aa14cf86ec86f2b652 vs 32b06aa8bc66762bbd6af15228072949

I keep getting a bunch of these, which turn out to be "customer cant delete messages from folder X". I just deleted all dovecot indexes (find -name dovecot* -type f -delete) from all users this morning and this is still happening.

Any ideas? Using maildir format