Any migration, in this case a mail migration to Office 365, will have bumps along the road that will lead to fixes and a better understanding of the underlying subsystem. Without stating the obvious, mail flow is perhaps the most important part of a messaging system. Any interruption, planned or not planned, can cause pain for the end user who does not receive or cannot send their email.
A bigger issue can be an automated system that sends out emails on a regular basis, nightly, hourly, monthly, etc. The automated system isn’t going to complain when an email bounces or is unable to get a message to leave its queue. It is up to the administrator to monitor this in some fashion in order to keep the automated system messages flowing.
I have a client that recently performed a cutover migration to Office 365. The mailbox moves went well, their ActiveSync devices connected, Office 2013 worked perfect, etc. However they had some issues with using their automated invoicing system. When using the local Exchange server, emails could make it to internal and external recipients. After the move to Office 365 we had set up a connector in Office 365 to allow for inbound or relay emails like this. It was configured for the NAT IP of the old Exchange server as we were using this to relay for a little bit while we moved all the other apps over.
However, we had one app that refused to work properly for external recipients. Test emails from the app to internal recipients, who had mailboxes on Office 365, worked perfect. When an email was sent to an external recipient the message failed to send. Luckily the application itself had some sort of logging and we were able to pick this up in the logs:
“SMTP returned error. 550 5.7.64 TenantAttribution; Relay Access Denied”
At this point we did two things, first enabled message headers on the inbound connector in Office 365, it was off for some reason.
We then sent an email from the application that would normally go to an external recipient to an internal recipient. Once the message arrived we examined the headers. It became obvious to us what the issue was, there was another IP that needed to be covered as an allowed address on the Inbound Connector.
After realizing that we had an additional IP that was NAT’d for this application (like a lot of companies they had a block of Public IPs, Exchange had one and one IP for computers without a specific NAT) we simply needed to add it to the Inbound connector in Office 365:
We also added the IP address to the SPF record in Public DNS like this:
v=spf1 ip4:, include:spf.protection.outlook.com ~all
Once applied testing confirmed the additional IP address and SPF change allowed email to flow from the application to external recipients.
I’ve talked to Microsoft about this and one other possible cause of this issue is if the application, when it composes the email, uses a domain other than what is on the accepted domains list. For example, if your tenant has 3 defined domains – BobsGarage.Com, TimsGarage.Com and JohnsGarage.Com and the application sending the email uses a domain like GaragePower.Com, then the connector in Office 365 will reject the email. If you receive the relay error, here is the order I would take for troubleshooting:
- Verify Sender address is using an accepted Domain (in the application, or message header)
- Send the email to an internal recipient – check headers for IPs to match in the connector
- Check your SPF record to make sure all IP addresses are listed as well
Again, there might be other causes of the relay issue, but these are ones I can confirm are a cause.
How to Allow a Multi-function Device or Application to Send E-mail through Office 365 Using SMTP