Yup, that'll get you stuck in spam limbo alright. Good luck climbing out if it if you're initiating conversations with anyone on Gmail or Outlook (or, even worse, corporate Outlook).
Those email services will usually have no trouble with replies to emails sent from their service, so if you get someone to email you first you'll save them the trouble of dragging your email from their spam folder to their inbox.
With Outlook, in my university the problem was that when we send emails they disappeared mid air, no bounce, no spam folder. The solution was that they must write an email from the Outlook address, after that we are added to a secret good list and we can write them.
I've had to figure out a problem with reaching university Outlook servers where the Outlook server didn't like the (spec compliant) way my email server was writing the From address and rewrote it halfway through the spam filtering chain.
Then it checked the DKIM signature on the message it REWROTE ON ITS OWN and decided that the signature didn't match, and rejected my email.
Corporate email stacks are hell.
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.
Do you have a write-up of this, anywhere? I'd appreciate the details (what format did it reject? what did it change it to? what version of Exchange?).
Not OP but I've also seen this. I think some of the servers in question were "outlook-protection" in their domain names. Some kind of managed service middleware in the stack to do additional scanning.
I second the request. A few years ago we switched to Google Workplace, but it would be nice to know. I would like to forward it to the sysadmins just in case we go back to our own server.