This started happening to me recently - although my emails seemed to be satisfactorily received, I had no record of sending them in my "sent items". This only happened when I used Outlook 2013 my laptop (on which I have Office 365 installed).
I searched in vain for any help on forums etc, and put in a call to support. They said they would ring me back (but haven't) - and I have continued hunting online, ultimately finding this thread.
I checked my settings in Options, and sure enough found the box for "save copies of messages in the Sent Items folder" in Options/Mail was unticked. Ticking it has solved the problem. I had not changed this setting, so I can only presume it was changed automatically as a result of some recent update of Outlook 2013 under my Office 365 subscription (I have Business Premium, as that's the only way I can host email using my own domain name).
Problem solved, but not thanks to Microsoft Support.