Research pointed to a couple of articles that all suggest checking the firewall:
- O365 sources blacklisted/quarantined by an over-zealous Fortigate IPS rule - https://pariswells.com/blog/research/office-365-failed-550-5-4-316-message-expired-connection-refusedsocket-error-code-10061
- Microsoft's own experience and recommendation - https://docs.microsoft.com/en-us/office365/securitycompliance/mail-flow-intelligence-in-office-365
It turned out to be not a firewall, but a case of asymmetric routing. Close enough. A new device has been introduced into the customer's environment to set up a VPN with a sister company at around the same time when the first delivery error reports started to came in. Setting up the VPN affected routing, resulting in egress/ingress SMTP traffic to/from the same source took very different paths.
Once routing has been corrected, email started to flow normally again.
Till next time.