Please answer this question:
Have you tried sending mail to recipients at domains other than live.com?
Also, what is the result of the following command:
telnet mx1.hotmail.com 25
root@localhost:~# telnet mx1.hotmail.com 25
Connected to mx1.hotmail.com.
Escape character is '^]'.
220 BAY0-MC4-F37.Bay0.hotmail.com Sending unsolicited commercial or bulk e-mail to Microsoft's computer network is prohibited. Other restrictions are found at http://privacy.microsoft.com/en-us/anti-spam.mspx. Tue, 3 Jan 2012 11:49:50 -0800
Connection closed by foreign host.
Is the result the same for you?