[Dovecot] Why do these keep showing up?

[Brandon Lamb]

2010-10-08 14:37:29 imap <hmarie at 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