SPF and Microsoft but not Microsoft

This is a crazy issue, I am hoping someone knows how to resolve. We have a Microsoft 360 account, but we host our own email server and our own Active Directory. We sync our active directory with Microsoft so that Teams and SSO will work correctly. But Our MX records and SPF etc all are to our company email server. Our email server is NOT exchange (thank god)

What is happening is Other Microsoft email Users, including Microsoft themselves are blocking our emails. I get a variety of bounces, either 550 errors, which typically mean blocklist, or mailbox does not exist errors. Which typically means they are blocking but reporting this way. I finally had one partner I had email issues with that was blocking my server, they said that I had incorrect SPF setup for my microsoft mail… (which I do not have) !! They send me this excellent article… Fix email delivery issues for error code 550 4.4.7 in Exchange Online | Microsoft Docs

This would help, if I was using Microsoft 360 mail! Since I am not. I am at a loss.

My guess is that Microsoft is arrogantly assuming that since I have a 360 account, I MUST be using there email and when email is sent from my own server it is flagging it as bad.

Anyone have ideas on how to resolve?

(oh yeah, this is so far beyond the standard support that they do not have a clue as to where to send it!)

I haven’t heard of a specific issue like this with Microsoft but seems feasible there could be a strange interaction going on since it is not very common to use a non-Microsoft system to host email when other services are hosted with Microsoft. At first glance it sounds like a configuration issue, but I’m assuming you’ve double checked everything already. Are you able to post a header and/or detailed error message of an email sent from our server that got bounced or blocked?