Just so you all are aware, if you're not already. There is a KB article on Mitel about Office365/Exchange 2013. It has really affected some of our customers since the sync just plainly doesn't work properly:
Published 09/18/2013 06:31 AM | Updated 09/18/2013 06:46 AM | Answer ID 5722
Issue with deleting messages in Office 365/Exchange 2013
Microsoft has changed the way Office 365/Exchange 2013 deletes messages and no longer sends an Expunge if deleting the message via webpage or outlook.
This affects the Mitel 5000 with Unified Messaging since there is no expunge being sent we do not know the message has been deleted via outlook or the webpage.
This does not effect deleting a message from the phone while listening to it. We do query the server with an expunge command the message does delete syncing with the outlook or webclient just fine.
Since this change is one that Microsoft made, we have no control over a time frame on a fix or changing this to work a different way with Microsoft Office 365/Exchange 2013.
