Please Note: In order for this to work, all of your clients must be using IMAP, not POP3.
1) On your iPhone, go to settings.
2) Select Mail Contacts and Calendars
3) Select the account you are having problems with.
4) Go to the Advanced section at the bottom
5) Located in the Mailbox Behaviors section, click Sent Mailbox
6) Make sure that the folder “Sent” is enabled in the “On the Server” section