I was really sick of POP GMail and the iPhone not just working. I found several types of hints online, and none would really work for my situation. I use POP on GMail so that I can get mail on my Mac and leave a copy on GMail's server for archive and search purposes, which I do endlessly. The subtle implication here is that I have about 2,500 messsages in there.
So I set up the iPhone and was all excited when it just took my accounts from iTunes and set them up. But I noticed one thing: even if I had Recent on, for some reason, my Mac and my iPhone would race to download a message and if one got it, sometimes the other did, and sometimes it didn't. I confirmed this to happen to other people via many furious and frazzled searches waaaay past my bedtime.
Another thing I found was that I'm not a super great typer on the iPhone yet, and there were some messages I'd want to read on the iPhone but respond to on my Mac. In short, for a lot of reasons, it wouldn't bother me to have messages on my GMail, on my Mac via Mail, and on my iPhone.
Further, even if I got some messages to actually find their way to the iPhone, I could read them okay, but when I deleted them, the iPhone politely asked me if I would like to load the next two billion -- I'm not exaggerating, it really said that -- messages. I found this to be a documented problem and, frankly, I was disgusted. Well, I figured out away for everyone to just get along:
Mac OS X Hints
http://hints.macworld.com/article.php?story=20080319064516225