Emails sent from Mail appears in the iPhone's sent folder and the web interface's sent folder.
Emails sent from the web interface doesn't appear anywhere - not in Mail.app's sent folder or in iPhone's sent folder.
I think that is where the problem is there is no synchronisation between the Sent folder on the server and your local one (eg, the one in Mail.app). Since you use the Google's SMTP server (and authenticate with your email address), sent emails get stored on the server but the two Sent folders (server and local) are not synchronized at all. Emails sent from Mail.app get stored locally and on the server but not because the folders are synchronized but because Mail.app adds it to the local Sent folder and the SMTP server adds it to the online folder.
Emails sent from the iPhone appears in the web interface's sent folder, but not in the Mail.app's sent folder.
I just read through your posts again, do you see anything in the Sent folder on the iPhone (emails sent from Mail.app or the web interface)?
Here are screenshots of my settings in Mail for my Gmail account.
http://img398.imageshack.us/img398/9772/gmailsettingsgb5.png
I'd think if you get the Sent folders (online and local on your Mac) synchronized, a restore of iPhone should get it working there as well. What might be still missing is this step:
In Mail's sidebar you should have a category called GMAIL (or the like), if you open all disclosure triangles there should be a Sent folder. Highlight that Sent folder (click on it), then go to the menubar: 'Mailbox' -> 'Use This Mailbox For' -> 'Sent'
You now should have a subfolder 'GMAIL' in your Sent folder in Mail.app:
http://img205.imageshack.us/my.php?image=sidebarka2.png
Don't get confused by my split personality.