there was a bug* in the server related to message counts that was crashing pop client connections, so some messages marked for deletion weren't getting deleted. it's fixed in the release due out soon (i.e. this week or so).
but you might also have a look
at this about corrupted uidl dbs
* bug 4033: Sync caused NPE in Conversation.removeChild()