AOL, the wonderful company that they are, require any mail to be sent to them to be from a server with a valid reverse DNS lookup (ptr) record. If you’re finding emails bouncing back from AOL (and some others) make sure your mail server’s domain name server has an an appropriate ptr record setup.

This is actually a fairly resonable anti-spam measure, however try finding out from AOL that’s the problem isn’t so reasonable. Anyway posting this as we’ve had this issue a couple of times and would make for a good reference.

To check you have an appropriate reverse dns setup, goto and enter the IP of your mailserver into the 2nd field in the middle. at the bottom if you’re okay it should say:
Answer: PTR record: [TTL 172800s] [A=]

if not you’ll get some message saying no reverse lookup or similar.