I am having MOUNTAINS of mail problems recently on my iPhone 4. The biggest, is that if I get more than 20 email messages, I have to turn the phone off and back on to read or delete them because it's like the phone has too many. Before you ask, there are NO other programs running in the background.
Second, messages I delete today, will show up again later this afternoon or tomorrow. Randomly I'll get messages from a week ago that show up as new messages. No, these DON"T show up on my Mac or other mail clients I use.
Third, occasionally I will get a message that can't be deleted. It will either just stay around or will say "No subject". Again, I have to turn the phone off and back on to fix it.
In short, my iPhone4 is acting like f*****g Windows!