Salesforce Email Relay with Microsoft 365

The Salesforce Email Relay feature doesn't support sending emails directly through Microsoft 365 Exchange (Exchange Online) to people outside of your organization and isn't recommended unless you have an on-prem or hybrid solution.

What errors might occur if I try to use email relay with Microsoft 365?
Microsoft 365, previously Office 365, needs to internally route and validate tenant emails that need to be relayed on to the Internet. Because of this requirement, some organizations can receive errors such as 'Relay Access Denied ATTR36' when emails are handed off to Microsoft message transfer agents (MTAs). This seems to be related to Microsoft's routing of email from shared IPs. Because of this, relaying email through Microsoft 365 can work inconsistently without the use of a standalone SMTP gateway for an organization's domain to pass email to an ‌Microsoft 365 tenant.

Note: Sending mail to users within your organization should work with Email Relay. See Option #2 on this Microsoft document:
https://learn.microsoft.com/en-us/exchange/mail-flow-best-practices/how-to-set-up-a-multifunction-device-or-application-to-send-email-using-microsoft-365-or-office-365