As easy as it is to bash MS, I won't. First of all as I have been using their products (as well as Apples) for the past years with great results and secondly a simple fix seems to indicate that they are right in blocking emails.
Check your domain with http://www.dnsstuff.com and you might get some warnings, especially about a reverse DNS /PTR record missing.
I contacted my VPS host and he added one for me (and also renamed the servername/url so it is actually valid. This might not be possible to do when on a shared IP by the way.
Their quick answer:
I have also configured RDNS for the domain ----.com, following are the info. It will take few hours to propagate globally
root@apollo [~]# host 12.345.67.89
89.67.345.12.in-addr.arpa domain name pointer ----.com.
root@apollo [~]#
Hostname changed to server.----.com, please do verify it from your end."
And just moments later all my emails to hotmail accounts did arrive and not even in the junk mail folder.
And no, I do not use any SMTP servers or plugins, just a standard WPMU install in this regard.
PS: Note that I had been spamlog free for 3 months, but got 3 spamlogs signed up just hours after this changed. Coincidence maybe as none had hotmail addresses.