I post this today because even after multiple restores I still have syncing issues with multiple mail accounts that that seem to just ignore the fact that I deleted a mail message. 10 times. The same message. I wanted to put my head through a wall.
Essentially I'll delete a message move on to the next then when I go to jump to another message, BAM! There's all the mail I just deleted.
Makes mail on your phone really (un) useful.
Chris posted that after upgrading to 4.1 his issues went away, but mine persist. Especially on my MobileMe account. Which kinda bugs me. A LOT!
Hope some of you find this link useful and entertaining.