I just went through the pain of switching to a new IP for my mail server a few months ago.
All major providers except Google were putting my messages in the spam folder by default despite me getting myself whitelisted in DNSWL and having proper FcRDNS, SPF, DKIM and DMARC configuration.
The IP was not in any reputable public blacklists, and the domain had been in use for many years.
Yes, I did. It was clean as far as I could tell. It was not just Microsoft, I also had issues with Yahoo, AOL and some others. The block I'm in is listed in some RBL called "spamgrouper"[1] but as far as I can tell nobody pays attention to it. No other lists showed any trouble.
All major providers except Google were putting my messages in the spam folder by default despite me getting myself whitelisted in DNSWL and having proper FcRDNS, SPF, DKIM and DMARC configuration.
The IP was not in any reputable public blacklists, and the domain had been in use for many years.