Before you just go changing hosts, you should know that Hotmail/Outlook is notorious for blocking emails for ABSOLUTELY NO REASON. And they make it impossible to be whitelisted. To be honest, the fix is telling people to stop using Hotmail. I've simply stopped trying to deal with them, and simply warn our clients. If people still want to keep using Hotmail, then they simply run the risk of not getting emails.
You can also get the IP address of your website (You can use our tool here to ping your website, if you don't know the IP: http://lg.la.wswd.net) and then run it through a few of the spam blacklist checking websites out there to see what comes up. If your IP is blacklisted, that is likely the problem, and it will be up to your host to get that IP de-listed. If not blacklisted, it's likely just Hotmail being stupid as usual.
That's fantastic! We have never been able to be whitelisted over there. Our emails can get through, but all are marked as spam, regardless of the content. You are literally the first company we've talked to in almost 20 years to say they've been successfully whitelisted.
Google, on the other hand, is virtually impossible to get to act on something. I was receiving my server messages for nearly 10 years on my GMail account. Then, out of the blue, they started rejecting them. After 3 months of tearing my hair out trying to get them to quit blocking my server messages, I finally went over to Outlook. Not an issue since then.
Any site that tells me I can't use a Microsoft email address doesn't get my registration or business.