Hotmail requires something called an 'SPF' record which stands for 'Sender Policy Framework'. This allows Hotmail and any other mail service that asks for an SPF record to check that the e-mail you've sent to them is coming from a legitimate server and isn't being spoofed.
To set up your own SPF record, visit your cpanel at http://www.yourdomain.com/cpanel/ and click on the 'Email Authentication' icon. Next click 'Enable' on the SPF section to enable the default SPF record. Usually the default setting is fine and that's all you need for Hotmail.
You can edit the settings once you've enabled SPF for more advanced usage of SPF. For more details on SPF, please visit http://www.openspf.org/