I encountered this error for a system relaying mail via Microsoft 365, sending mail to users within the organisation was working as expected however the sending system was getting the error below attempting to send to external recipients.
451 4.4.62 Mail sent to the wrong Office 365 region. ATTR35.
There is support documentation for this exact error and the configuration of the connector that had been created appeared to be correct. It was only when performing a message trace on some of the emails that were working that the reason for the error became evident – the IP address the mail was being sent from wasn’t the expected IP address and the connector required updating.
The reason the mail delivery was failing, is that Microsoft 365 was treating the mail being sent via the smart host as mail to be delivered to internal recipients, and as the connector didn’t have the correct IP addresses mail intended for external recipients was being rejected – with what appeared to be a cryptic non-helpful error message.