A few months ago I had a slew of customers with the same problem. I was able to find a solution that fixed the issue for all of them. See below:
When setting up email integration with Office 365 there are a few considerations:
1) - Mitel recommends Mitel 5000 release 6.2 or later software for integration with O365.
2) - server address must be entered in the following format - <domain>.mail.protection.outlook.com. So if the company's domain is xyzinc.com, the address would be xyzinc-com.mail.protection.outlook.com. Take note that the domain uses a hyphen in place of the dot.
3) - port should be set to 25
4) - username and password seem to be required by the Mitel server. Despite what the server admin may assert regarding authentication it is best to enter an account and password. Ask the server admin to provide account/password. Rel 6.2 and higher will generate INVALID APPLICATION alarm A028 when account info is missing from the email gateway form.
5) - a connector is required in the O365 environment to enable mail relay. The following article seems to describe the setup process quite well
https://technet.microsoft.com/en-us/library/dn751020(v=exchg.150).aspx