Zend certified PHP/Magento developer

Emails getting a “Relay Error 550 5.7.367” on Office365

I am working on an odd issue that is occurring over the past few days with receiving undeliverable email errors. The error is 550 5.7.367 (“<email> is not authorized to relay messages through the server that reported this server”).

The odd part is, this error is actually being shown when emails are sent from different domains (a Microsoft365 tenant and, here’s a blast to the past, a @msn.com domain). Different devices are being used, as well (laptop/phone).

My only thought is that, where these emails are sent from, the ISP recently changed from Comcast to Hotwire Communications who laid out new fiber lines. My thought is that there is something on the receivers end of the email that doesn’t like the new IP address or ISP, but personally have never ran into this issue before and figured someone here may be able to guide me in the right direction! I’m considering setting up a VPN connection to mask the IP, but I am unsure whether this will actually do anything.

I should note that the emails are being sent both from and to different domains and email addresses with the same result.