Go to: http://www.openrbl.org and make sure your main server IP address and/or hostname is not blocked or blacklisted on any of the popular DNSBLs.
Although your main IP or hostname might not be listed there, it doesn't mean that it is not blacklisted or negatively scored by AOL or Yahoo or Hotmail or www.rr.com. It is likely that AOL or Yahoo or Hotmail or www.rr.com negatively scored your server due to past traffic from that IP address before your server was using it.
Disable the feature Autoresponder on your server.
Make sure your domain has an appropriate SPF record ( http://spf.pobox.com).
In some situations, you might have dedicated IP for your site and your MX and A records point to that IP. That IP address is NOT the main IP address for the server. By default, on a cPanel powered server, the main IP address is the one which sends out mail. So if the main IP of the server is 60.70.80.90, then you need the following as a minimal SPF record for all domains on that server:
"v=spf1 a mx ip4:60.70.80.90 -all"
MSN/Hotmail recommends using -all terminators in the SPF record.
Make sure the IP address that your server sends mail from (which would be the main IP address), has:
Valid reverse DNS (rDNS); and
That rDNS is reflective of your hostname , rather than some generic record that your upstream IP provider has put in place.
Run the following two commands to see if your hostname is associated with the main IP of your server:
nslookup your.hostname
and
nslookup YOUR_SERVER_MAIN_IP
(where YOUR_SERVER_MAIN_IP is the main IP address of your server). The system should return your.hostname
(Even after you've followed all of the above instructions, you and your users may find that their email does not arrive, or ends up in the Spam folders of Hotmail, Yahoo, AOL, and so on. In this case, you need to submit a ticket with MSN/Hotmail Technical Support at: http://support.msn.com/eform.aspx?productKey=edfsmsbl&page=support_home_options_form_byemail&ct=eformts
Make sure your users aren't forwarding all of their email, which might include spam, from their accounts hosted on your server to an @aol.com or @yahoo.com or @hotmail.com email address. That will surely cause future emails from your server's IP address to be considered un-safe or spam by those entities.)
If this is too complicated, submit a ticket and we will do it for you.