Recently, one of my customer is having issue on the Exchange Online.
The case is that the company is using a 3rd-party notification system to send out alerts to internal staffs everyday, somehow, he found that the messages are displayed to be blocked in the 3rd-party reporting system.
We have double checked the allow-and-block in Mail Flow, and even set the domain of the system to bypass the spam filtering, however, it does not help.
Finally, I came up with a solution.
When you send an email through a 3rd-party system (it depends), the email is transmitted through the 3rd-party servers instead of Office 365 server. Email can be easy to forge, so the system will automatically authenticates all emails sent through its system using multiple authentication methods to help improve deliverability.
In order to let it authorized in Office 365, what you need is adding the DNS record to allow the 3rd-party domain in SPF record.
v=spf1 include:spf.protection.outlook.com include:3rd-party.domain.com -all
That did the trick!