We've got some web servers with FTP-Only access set in "paranoid" mode. I.e., in order to gain access, the machine from which you are coming must have an IP mapped to it and the IP you have must be mapped back to the same domain name.
This was causing problems with a particular customer who was attempting to gain access from the provider ctonline.net. They claimed that they had the PTR RR's set up correctly, and in fact, when I queried their nameservers directly, I did see that they had entries.
The problem turned out to be that the entity providing them their backbone connectivity was not acknowledging them as authoritative for the class C's that they were using. Thus, their DNS information was not being propagated to the Internet.
You may find the following 2 links useful. It's email that we sent to ctonline.net's system administrator describing and pinpointing the problem. It's probably a good idea to check your system in the same way, replacing yourdomain.com with ctonline.net. I've come across this 3 times in the last 3 weeks.
World | Inch