Solution!
I, too, was having this problem and think I finally found (a strange) solution!! It's sort of annoying but you'll only have to do it once to fix things.
First of all, make sure you have Recent Mode turned on. Now set your mail settings to 200 Most Recent. In your advanced settings make sure you have the "Delete Messages: Remove" setting to anything other than "Never"... I used "After One Day" (BE SURE NOT TO CHANGE THE "DELETE FROM SERVER" setting, though... otherwise you will lose your messages for real!!!).
When your Gmail updates it will only download the first 50 messages. Now delete them all (or at least whichever ones you don't want/need anymore. More than likely this will be enough for it to realize you don't want any more messages, or the recent setting somehow discriminates how old a message cna be to be sent to your iPhone, because once this happened I didn't get any more messages. In fact, there was a "Get 50 More Messages" button in my inbox, but clicking it didn't get me any more messages, it actually just caused that button to go away after a reboot!! If you find that more messages DO come in, just delete those too, you probably just have more "recent" messages than I did !!
I know this is a pain, but I am 90% sure it will work ! Now I only get new messages to my iPhone... In summary:
01)Settings>Mail>Gmail>Advanced>Deleted Messages: Remove After One Day
02)Settings>Mail>Gmail>Advanced>Delete From Server: Never
03)Settings>Mail>Gmail>Advanced>Use Recent Mode: On
04)Settings>Mail>Messages>Show: 200 Recent Messages
05)Mail>Gmail>Inbox... Update and download messages
06)Delete all the messages
07)If/when you see "Get More Messages..." click it
08)If more messages come delete them too
09)That should do it!!!
Please let me know if this works for everyone else too !!
--
breathmint