Those of you with the problem: are you using "recent" mode? I think that's what triggers it. The problem is, if you don't use recent mode, you only get your emails on whichever device you check first (so if you get it on your iphone, it won't download to your computer). So it's really a pick your poison kind of situation, and both options are annoying.
What I did was to get a free AOL email account and forward all of my gmail to that. My iphone and my mac are both set up to receive the AOL mail (which will include everything from gmail) and then to send new messages using my gmail account.
The result is that I have IMAP email (synced across devices - so I get every message on both iphone and mac, and I can see messages sent from either place on both devices), all of the mail still appears in gmail's web interface, AND I don't get my own sent messages sent back to me. Best of all, the AOL is completely invisible to the outside world. People email me at my gmail address and get a response back from the same. There's no indication that it's going through the AOL severs at all. I highly recommend this solution.
edit: ah, siurpeeman beat me to the "recent" comment, and he even had verification! So you can turn that off, but then you won't get all emails on both devices.
