Same experience here. I did everything right and could send email from my VPS to basically any other provider, except Microsoft. I had to give up and use the SMTP proxy provided by my VPS vendor to not have all my emails to @outlook.com or @hotmail.com end up in spam.

I stopped caring for outlook.com and hotmail users. If they don't receive an important message and get back to me because of it, I just blame their spam filter configuration, and tell them to get a proper email provider ;)