Do any of the users have "Leave copy of message on server" in their mail client preferences?
Also has a reconstruct -r been tried?
If it has not I recommend running one on the entire store. This will fix any problems with the mailbox index files which could be causing this problem.