AOL is not accepting e-mail...
"AOL is not accepting e-mail from my server" "Road Runner is not accepting mail from my server".... etc Sound familiar? This is a pretty common question in the newsgroups. I have been battling this issue myself with one of my own customers.
Some ISPs (Time Warner's companies are notorious for this) check to see if your mail server has a PTR record. Does your server have an PTR record for it's public IP address? You can easily check here:
Plug in your IP address in here to see a fairly comprehensive test. Ideally, your PTR record name (eg mail.somorita.com) should match the HELO or EHLO banner that your mail server sends out. Some mail servers will even reject your message if the EHLO banner does not match your PTR record. Fortunately, most don't.
Now comes the hard part: how do you assign a PTR record for your public facing IP address? You usually don't. The owner of the IP address must do that. That is almost always your ISP. Contact your ISP, tell them that you need a PTR record for your public IP and tell them what you want it to be, such as mail.somorita.com.