This has plagued us for years. We send quite a lot of transactional email (about 150k emails per day), and there have been several times where Microsoft blocked our server. Usually it is because Microsoft has banned an entire netblock, that our server just happens to be sitting in. I have seen them do this to IPs fro Hetzner, Linode, Amazon AWS (SES), etc. And yeah we've signed up for their junk mail reporting service, and we have all our DNS records dialed in perfectly.
I even went as far as signing up for Azure, in the hopes that if I sent from a Microsoft IP it might not get blocked. But I didn't make it very far, every step of the way was like watching paint dry while the interface loaded or did something. Once I finally got the thing set up in order to send mail, the API was so molasses slow that it couldn't handle our mail throughput. Meaning it would take about 30 seconds to send each transactional email because of how slow their API is. Well that's only 2880 emails per day, that is not a reasonable send rate at all.
I have even lost customers over this mess, it's really hard to explain to them that they can't receive our email because of their provider and not us. Especially when Microsoft has the audacity to return: 250 OK Email Queued (but then not deliver it anyway!)
If anyone has any solutions to this mess I am all ears!
It's almost certainly because your customers are reporting your emails as spam by moving it into the junk folder which is training their systems.
Once enough of your customers do this to cross a certain threshold, you are identified as an undesirable sender and QED.
It happens at scale.
There's like a middle scale where you're not big enough that Microsoft will go out of their way to whitelist you, but you're big enough that your "send to junk" rate is just high in terms of absolute numbers.
It's certainly not a ratio, it must be based on absolute numbers because I've seen it too many times across too many companies, and the only ones that get away with it are extremely low volume.
Once you have 1,000,000 mails, even a 0.1% mark as spam rate is 1,000 emails. - and some people treat mark as spam as their delete button, certainly more than 0.1% of people. Don't ask me why.
EDIT: on inspection; it's worth noting the mechanism is even more insidious than "people mark you as spam". Microsoft also weighs delete-without-opening as a negative signal. So if you're sending transactional mail (receipts, shipping notifications, invoices) and your users get exactly what they wanted, feel satisfied, and bin it without opening. You've just taken a reputation hit for doing your job correctly. The senders most at risk aren't the ones sending rubbish.
[dead]
I do not think that is true.
Once when this happened to me a couple of years ago, it was the opposite.
My e-mails were put by default by Microsoft as spam into the junk folder, without the customer knowing anything about this.
After I succeeded to notify him about this, he searched there the e-mails and marked them as "not spam", and then he received my following e-mails.
So initially the customer did nothing and was not aware that some of the e-mails sent to him are classified as spam, and he had to do active efforts to override this default action by Microsoft.
There was absolutely nothing suspicious about the e-mail messages classified as spam in their content, their only fault was not coming from one of the few major e-mail providers.