I have no idea what the first person to reply to thsi thread is talking about, he is on some rant that makes little sense and did not answer the question…
To start with, reverse DNS, or inverse DNS, or your .in-addr.arpa records are what AOL is talking about here. You can read more about them at the link below:
http://www.dnsstuff.com/info/revdns.htm
Basically, AOL takes the position that if you run a email server, when you send email to AOL through that email server, they take the IP address, invert it, and make sure there is a corresponding DNS entry for that IP address, also called a PTR record.
You can do little to fix this issue on your own. But you can do some. The first thing you can do is simply not send email through whoever you are that has DNS not set up correct. That will solve the trouble in the meantime.
Next, there are 2 places that control the rDNS, it could be the people in charge of DNS for the domain itself, or it could be their IP provider. Everyone does this a little different. It is called delegation and determines who can control this. Most people get to maintain their own DNS as they see fit, rDNS on the other hand, can sometimes be delegated and allowed to be controlled by the DNS admin for the domain, or it can be controlled by the upstream provider. I would almost be willing to bet that the case you are faced with is one in which the person in charge of the email server actually does not even have the control to add a PTR record if they even wanted to. In this case you are in luck, somewhat, You can go to arin.net and enter in the IP of the SMTP server and see who own that IP space. From there, you could send a email to that admin and ask them if they will simply fix the problem. some people are under the impression that rDNS must be a “pretty” name but in the case of AOL, it just needs to be defined, they do not care what the actual hostname is. Either way, it is something that most people can deal with in about 10 seconds. It is a very simple matter.
Also, try entering in the IP of the SMTP server into dnsreport.com and it will tell you what the trouble is and even point you to fixes, you may want to give this info to your mail servers admin.