I've got a client, who is on the Office 365 E3 plan, and they have some Samsung Galaxy S Android phones.
All working great except for one of the phones.
With this one phone you can't send emails as they just get stuck in the Outbox.
It says it is sending the messages but they never go.
This user can send from Outlook and Outlook Web Access without a problem so don't think it is a problem with their Office 365 account.
I've removed the Office 365 account from the phone and added it again but it made no difference.
The phone receives emails fine and syncs calendar etc.
It used to work great, and one time, after the problem started, it did suddenly work again for about a day and then the problem came back again.
I have tested on 3G and wifi.