I am also facing this issue, both on old and new servers/domains that I setup.
The error is the same even with a new IP addresses and based on what I read in the troubleshooting page:
Are you sending email from new IPs?
IPs not previously used to send email typically don't have any reputation built up in our systems. As a result, emails from new IPs are more likely to experience deliverability issues. Once the IP has built a reputation for not sending spam, Outlook.com will typically allow for a better email delivery experience.
New IPs that are added for domains that are authenticated under existing SPF records typically experience the added benefit of inheriting some of the domain's sending reputation. If the domain has a good sending reputation new IPs may experience a faster ramp up time. A new IP can expect to be fully ramped within a couple of weeks or sooner depending on volume, list accuracy and as long as their junk email complaint rates are kept at a minimum.
If you ask me that makes no sense.. I buy a new domain name and set up a new server with a new static IP for a client and they just block its mail system right away.. What am I suppose to tell my clients? To just wait and see if microsoft will trust our IP in a couple of years?
Which is also not likely to happen.. I own some servers for years and their IP is still is blocked, even though no spam is sent from domains hosted there. And of course, it's not possible for the client to wait, because they need to run their business through their website, eshop, service etc.
This is one of the oldest issues for microsoft associated email accounts, and I don't see it getting fixed for decades now.
So, the only "solution" I can see is to just mention on websites that microsoft email accounts are not accepted, for reliability issues, as they are the only ones that by default have trouble accepting emails. Use anything else and your problem is solved.