An IT technician migrated a customer over to Office 365, including using the hosted Microsoft Exchange service for email. He followed the right steps, verified their own domain name, adjusted the MX record and added the right SPF entry.
However, some people sending to this email domain were receiving a delivery failure report error (though some people could send to them successfully):
SMTP error from remote mail server after RCPT TO::
host recipientdomain.com [223.99.99.99]: 550-Please turn on SMTP Authentication in your mail client.
550-delivery5.spamserver.com [116.99.99.99]:54447 is not permitted to relay
550 through this server without authentication.
The senders were not isolated to one ISP.
Note in the error (and in the failure headers) there’s no mention of servername.mail.protection.outlook.com, which are the actual Office 365 email servers.
The ‘relay’ error is off-putting. What we actually have here is a DNS lookup failure. The sending server is not connecting to the server named correctly in the newly updated MX record, but is trying to connect to the A record entry. How do you even begin to fix that?
Well, in this case, you don’t. It turns out that the MX record had been changed less than 24 hours before the error was reported. According to the official instructions at http://office.microsoft.com/en-au/office365-suite-help/create-dns-records-at-any-dns-hosting-provider-for-office-365-HA103479204.aspx
“Typically it takes about 15 minutes for DNS changes to take effect. However, it can take up to 72 hours for a changed record to propagate through the DNS system.”
And this is the key. It’s good practice to change MX records on a Friday after 5pm, to allow them the weekend to propagate. After a little more time had passed, the ISP’s DNS servers had received the MX record update and the sending errors disappeared.