yes, indeed, even if you have perfectly clean IP space and do everything flawlessly, expect months after you put it into production before email to/from anything microsoft hosted starts to work properly.
I had lots of issues with MS, only with recipients in their free services like outlook.com, Hotmail and live. Always soft blocked because they said my mailserver didn't have enough 'reputation'. Opening a ticket got it unblocked but it happened again a few months later. Drove me crazy. Strange enough corporate O365 recipients (my work uses it) worked fine always.
I'm 100% sure no spam was sent by my server as everything was logged.
Clear blog! But I had all that. SPF, DMARC etc. I had perfect scores on all the online checkers and I was not on blocklists.
The problem is MS just ignores all that and built their own system, one that works on reputation. If you don't send a lot of mail you don't build up reputation and they block you. Over and over. Even if you never send any spam.
The big names just don't care about standards and they have the market share to simply ignore them.
I remember I need to file a complaint with Microsoft. You can also register a few outlook.com accounts and manually train the system :)
Seriously, the whole SPAM situation is way overrated. In the name of fighting SPAM, they (the big email providers) blocks us, but they let all the ads in? To add injury on top of insult, they are lenient for paying corp accounts but very strict for "free" personal accounts?
If this does not tell you what "free" big email providers are, nothing will.
Or you can cheat and use sendgrid or mailgun, but that is like caving to the dark side.