Since 3 days or so (since I have my iPhone …), Gmail doesn't reliably save my outgoing email anymore (sent through the web interface from my notebook). Emails of mine that aren't responses to anything don't appear under "sent." What could be going wrong?
When you say “sent”, do you mean the “Sent Mail” folder within Gmail or do you perhaps mean a folder on your iPhone?
Suggest you do a test to see if the problem is that the sent email never reaches the “Sent Mail” folder or if it initially appears in “Sent Mail” but subsequently gets moved out of that folder when the iPhone synchronises with Gmail. You could do that by temporarily switching off your iPhone and checking the “Sent Mail” folder, immediately after send a new email. If the problem occurs before the iPhone synchronisation with Gmail then it is a Gmail configuration problem. If the problem occurs after the iPhone synchronisation then it is an iPhone configuration problem.
Check "Recent mode" on iPhone.