The first step is to make sure your server is not blacklisted, which is pretty easy to do. Just click that link and type in the IP of your server.
The next step is to make sure the domain name of the e-mail address you're sending from routes back to the IP of your SMTP server.
In other words, say your sending e-mail from admin@mysite.com. Open the command line and ping "mysite.com" like this..
C:\Documents and Settings\Justin>ping mysite.com
Pinging mysite.com [64.136.24.162] with 32 bytes of data:
Reply from 64.136.24.162: bytes=32 time=72ms TTL=240
Reply from 64.136.24.162: bytes=32 time=95ms TTL=240
Reply from 64.136.24.162: bytes=32 time=84ms TTL=240
Reply from 64.136.24.162: bytes=32 time=76ms TTL=240
Ping statistics for 64.136.24.162:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 72ms, Maximum = 95ms, Average = 81ms
We can see that the IP address that routes back to mysite.com is 64.136.24.162.
If your SMTP server is not on this exact same IP your e-mails might be showing up in the spam folders of Hotmail and Gmail. In this case, your SMTP needs to be on 64.136.24.162—the IP of mysite.com. If it's on 64.136.24.163 then don't be surprised if you're showing up as spam.
Why? Because spammers often spoof e-mail addresses to make it harder for them to track. In their e-mail headers spammers might claim their spam is from admin@idontspam.com, but it's really coming from the IP of lovestospam.com. These days, most mail servers will double check the domain name of the "mail from" against the real name of the server. If something looks fishy in the spam folder it goes.
So make sure the IP of your SMTP matches up with the domain name you claim to be sending from.