As fritzo indicated, the error given back indicates that you are not connecting on port 25, but rather 23, which is telnet. The syntax you are using is not correct for Win*.

Microsoft Telnet> o mx.hotmail.com 25
Connecting To mx.hotmail.com...Could not open a connection to host on 
+port 25 :
Connect failed
Microsoft Telnet>
[download]

The connection failed due to my environment setup, I expected that, but the important point is that it failed on the correct port...