@pluralistic @Aaron @kat This behaviour from Microsoft drove me to give up running my own email server.
In addition to rejected outgoing mail, I began to suspect that some incoming mail was being silently dropped by certain operators, though I never did confirm or reject the suspicion. It's possible I imagined it, but paranoia is just one outcome when a crucial communication medium is interfered with as a matter of course. Which is why we need companies like this to be more accountable for their actions.
I didn't get any movement from them when I submitted a complaint, and this was one reason I eventually gave up and moved to a European SaaS email provider. In fact, shortly after switching, even they had one of their IP addresses blocked for a few days. They were cloud hosted, so I expect there had been bad behaviour from a tenant in the same IP block. I think I've changed provider since then.
I expect you'll get things resolved more easily, but it really shouldn't require contacts in the right places to get this sort of issue moved along.