I think figured it out. The original problem was that Mail.app was not using Gmail's smtp server. In the account preferences in Mail I have checked the box which says: 'Only use this server' under the pop-up list which has Gmail's smtp server selected. But examining the full headers of emails sent via supposedly different smtp servers (via different email addresses with all have that 'Only use this server' checked) and emails sent via Gmail's web interface gave me the strong indication that Mail.app is not using Google's smtp server.
Lo and behold, once I switched between my corporate network and a cellular-modem based one which caused Mail to fail to reach the smtp server (inside my corporate network only my corporate smtp server works and outside every smtp server except the corporate one works) and therefore brought up a dialogue which allowed me to choose the smtp server and I selected Gmail's smtp server, my sent messages showed up in Gmail's sent folder.
Even better, after restoring my iPhone (syncing wasn't doing the trick), emails sent from my Gmail account on the iPhone show up in Gmail's sent folder (and Gmail's sent folder also shows up on the iPhone).
As usual, if you for your life's sake cannot figure something out, most likely something you consider a fact is actually not the true. I was assuming that Mail was using Gmail's smtp server, that is what I told Mail to do. But apparently, once Mail fails to reach an smtp server and you tell Mail to use another it continues to use this alternative server forever until it fails to reach this one and ask you again (and that is the only way to reset it). And more importantly this alternative smtp server gets carried over to the iPhone. Even more sneakily, if you check the smtp server setting on the iPhone it still reads the 'correct' one but it is using in fact another one (visible from the full headers of the received email).
Getting Mail to use the correct smtp servers is its own pain in the butt. And after the umpteenth restore with everything working now, I now unchecked the option to sync mail accounts (since I keep switching networks on my Mac, I'm sure to end up with the wrong smtp servers associated with my email accounts).
