Office 365, Email, Outlook, Messages aren't sent and appear in outbox folder
Go to Tools -> Options, and then click on the Mail Setup tab. You should see a check box for "Send messages immediately when connected." Make sure this is checked. This is checked by default.
Sent messages in Microsoft Outlook appear in the Outbox folder, instead of the normal sent mail folder. This is accompanied by a message saying that the messages were not sent.
You will also want to check to make sure that Outlook is not in "Work Offline" mode by going to the File menu.