Typically this is a missing A or MX record but in Office 365’s case where you are the sender and have a registered domain with O365, MSFT can block your outgoing mail if a user has:
- an infected computer sending spam
- DMARC not configured and a spoofed address is sending spam
Firstly, I would ensure that you have SPF, DKIM, and DMARC configured. That way you can be sure that no spoofing is occurring. Then, that only leaves “infected machine”. I recommend using a utility like MXToolbox to ensure that everything is configured properly. It’s best to find the infected machine and repair it as well as change the users password.
Even if you don’t have your mail hosted with office 365 all it takes is to have your domain “authenticated” with O365 for you to be able to administer the necessary security settings to correct this issue. If you are having the issue and don’t have office 365 then you need to use the delisting service located here. https://sender.office.com/
Historically, you could go here as of 2017
and you would have seen
and you would have clicked on “action center”
I’m not sure when this notice became available but it was absolutely necessary that it did:
By clicking on the “Anti-Malware Page” which actually takes you to “Office 365 Security and Compliance” -> Threat Management -> Policy
The canon way to get their from office.com is to then click on “Admin” and then the security admin panel. Or, you can go to protection.office.com.