Does this happen just for Hotmail, or for all emails you send to remote servers?
You can search for Hotmail here on the forums, there are a lot of threads already about this.
Also, make sure that your server isn't blacklisted:
http://mxtoolbox.com/blacklists.aspx