This issue is not with sending or receiving mail.
The issue is that 'sent' items on the iPhone are saved to a different 'Sent' folder than the exchange folder structure. This appears as 'Sent' with a paper airplane icon in the folder structure of iOS mail when viewing the folder where messages sent from your phone appear. There is another 'Sent' folder with a folder icon where messages sent on other Exchange client email appears.
If you have an IMAP account setup, you can specify what folder stores sent messages in the Advanced mail settings under MAILBOX BEHAVIORS. On Exchange email accounts, the MAILBOX BEHAVIORS section doesn't exist under advanced settings.
When looking for sent emails in an exchange client on desktop, the sent messages from iPhone look like they were never sent - they were, they are just getting stored in a location inaccessible to the desktop client.