I realize this thread may be a bit old, but I wanted to add my findings for future readers. I have a Verizon XV6700 and often see the exact same behavior (deleted messages aren't really deleted, so they re-appear with the next synchronization). I do think there is something about the IMAP server which at least contributes to the situation, though it may not be entirely to blame. I say this because I have one account that connects to an exchange server at work, and it always deletes properly. By contrast, my personal domain is hosted by ReadyHosting and ~80% of the time it does not delete problem. Then some days, just to really piss me off, it starts to work again.

At a mimimum, it's not just the Q, and it's not just the 6700. It may be more of a WM5 thing when combined with a non-exchange IMAP server.