I operate a website http://www.mp3crib.com that requires users to validate accounts. Unfortunately my email server was looked upon as a spam server. Though not blacklisted providers such as AOL and MSN/Hotmail were sending my emails directly to users spam folders. Luckily there are steps you can take to prevent this:
Setup reverse DNS
Contact your ISP about setting up a reverse DNS record. This only takes a couple of minutes but it has the biggest impact on legitimizing your email server. If your ISP is like mine they will have a web based management console that makes the process idiot-proof.
Setup an SPF record
MSN/Hotmail as well as other email provides are big on this one. openSPF has a wizard that creates your SPF record for you. You’re domain registrar should have an option to add this record into your account or you can add it into your BIND or other DNS server.
http://openspf.org/
Contact AOL directly
You can contact AOL directly about getting on their “white list.” I was amazed by their response time, I was on their whitelist within 24 hours.
postmaster.aol.com/
Contact MSN/Hotmail
Microsoft also has great response time.
http://postmaster.live.com/Services.aspx
Other
Make sure your email server is not an open relay. The easiest way to do this is to restrict sending of emails via your server to the localhost and then use a web-based MTA such as squirrelmail or roundcube. Create some test accounts on gmail, yahoo, aol, and msn to see if your emails are going into spam folders. If they are then get in contact with these providers and see what you can do to resolve the issue.