Binary package hint: evolution
Allready tried all possible solutions (removing index files, exporting and importing mails from mbox format), but no luck to get rid of this annoying error.
There are lots of people getting this error for a long time, but no working solutions so far...
Also after deleting index file, all messages, wich are flaged as important, loses their flags and read/unread status. Also these duplicate mails, when this error happens. Imagine what is going on on a folder with 3k or more mail messages.
Maybe the problem is in Evolution startup while messages index check (or index rewriting), when at the same moment new mails are arriving and therefore not having proper access to message index (mail counts and status in Inbox by example). I have noticed, that this bug appears mostly when Evolution is started and there is a new mail on server to download. I think so, because it never happened to any other folder (at least for me).
There are new version of Evolution (2.10.2), but it's available only on Gutsy at the moment (I have Feisty Fawn 7.04). Maybe this bug is fixed there, don't know.
Thanks for the bug report. This particular bug has already been reported, but feel free to report any other bugs you find.