I offer this account of trying to address a known (and I would say, severe) bug in the iPhone 4 mail software, in case it's helpful to others:
Ever since I upgraded my iPhone to IOS4 (the latest version of the phone's operating system), the Mail application has been flaky when it comes to syncing mail messages via IMAP. Duplicate messages, empty/blank messages, messages dated 12/31/1969, messages that are deleted and then re-appear, and so on.
At first I thought it might be my phone hardware, which had been cursed from the beginning (a story for another time), but after that phone died and Apple replaced it with a brand new one with fresh firmware and settings, and it STILL happened, I was convinced it's the software on the phone. Other people are having the same issue all over the place. But it can be hard to make Apple believe this - said the Apple Genius Bar worker at the Apple Store in Chicago, "they're probably all just using the phone wrong." Wha?