I manage a couple of servers and 3 of them got flagged the same week by Microsoft and block all email these servers send and we get these errors :
550 5.7.1 Unfortunately, messages from [xxx.xxx.xxx.xxx] weren't sent. Please contact your Internet service provider since part of their network is on our block list (S3140). You can also refer your provider to http://mail.live.com/mail/troubleshooting.aspx#errors.
2 of these server are dedicated servers (with WHM) that host around 70-90 clients and the other server is a VPS (with Plesk) for a single client.
On the servers with WHM, I checked the Mail Delivery Reports and I don't see sign of spam. Our abuse@ accounts only got 4 complaints last month.
I checked the reputation of the servers on talosintelligence.com and all servers got a "Good" email reputation.
I made a blacklist check on mxtoolbox.com and they are not listed on any list.
We contacted Microsoft multiple time and they always return us saying that the "IP do not qualify for mitigation at this time" and that they cannot give us more information.
We made multipe tests on glockapps.com, the test email got received without problem with every mail service expect for the ones from Microsoft. For Outlook, live, hotmail the message are never delivered and for Office365, it get spammed.
We have multiple client that call daily to know what is happening and frankly, I just don't know. Everything seems fine and Microsoft doesn't seem to want to help us.
Thank you
EDIT: Got contacted by OVH, Microsoft blocked a bunch of their IPs, so it was not on our side.