Now, I got it working by syncing the email account from Mail.app to the iPhone. If you enable this syncing, all email accounts set up on the iPhone will be replaced by the set of accounts you choose to sync in iTunes. If you are willing to do this, here are my settings:
- in Mail.app, for the account in question: (a) check the box that says 'Store messages on server', (b) For outgoing server, select the SMTP server associated with your account (you most likely did these two things already, otherwise you would not have been able to see the sent message in the browser)
To make sure these settings are synced, I'd suggest you first deselect all accounts in the syncing preferences in iTunes, do a sync, and then enable the accounts you want to have on your iPhone.
Now, the first thing you should see is a Sent folder for that account on the iPhone, this Sent folder should contain all the messages you also see in the browser. Secondly, you should also see messages sent from the iPhone.