Comment by vel0city

This has almost always been the issue when working with clients on why our emails never appear. In the end they have some weird middleware that rewrites things and then the next level of the stack sees the middleware as the sender of the email for our domain which fails as it's not an approved sender by SPF and dkim signatures don't validate.

A fresh, plain setup on office 365 doesn't fail, but however their security department reconfigured things causes it to fail.

I've never been on the configuration side of M365 email like that, only basic cheap tier stuff and only briefly. I can't say what they're doing, but the same settings sending to practically any other email provider or even other 365 tenants works perfectly fine.