Tady je každá rada drahá. Máš možnost přidat domény do whitelistu, máš možnost vypnout SFP/DKIM kontrolu.
EXO je samo o sobě poměrně exotická služba.

Osobně bych začal tím, že bych se zkusil "vrátit v čase", tj. vypnout všechny novější nástroje jako SFP/DKIM apod. a nasadit nějaký DNSBL systém + greylisting. Poměrně dobré kompendium postupů včetně návodu máš zde: https://www.undocumented-features.com/2019/08/13/exchange-online-protection-eop-best-practices-and-recommendations/

P.S.: že je podpora MS v koncích, to bych řekl, že je pro ně typické.