I registered a domain from an ISP/Hosting company, and leased a Virtual Private Server from them to operate my website.
AOL and other mailservers won’t accept email from my website because it does not have Reverse Domain Name Server Lookup set up.

Everything I have read says this is the responsbility of the ISP that provided the IP addresses and Domain Name Servers.
The company says it is *my* responsibility, and I will have to dedicate two IP addresses and build this into my Virtual Private Server, and will have to upgrade to 0 month to handle the "extra load".

I say it is their responsibility to set up reverse DNS look up, given that they provide the DNS servers and the two IP addresses so that the internet community can translate my domain name into an IP address.

If you do a "Who Is?" lookup, it returns two nameservers operated by the ISP, and their dedicated IPs for them. I figure a reverse lookup should lead to their servers also.

Please help me sort this out.
The first answer does not seem to help.
I have gone to www.dnsstuff.com, and there is NO reverse DNS look up registered. The people I lease my virtual server are providing the DNS servers, but they continue to claim that I have to configure my own DNS servers if I want reverse look up. They claim that the servers they are using as my Domain Servers do not provide the reverse look up function (they claim it is disabled). They claim I am the only client who is having this problem, and that it is either AOL’s fault for insisting on reverse dns lookup before acceptine email, or it is responsibility to set up reverse dns lookup if I want it.

I am going nuts with this…how can they possibly be selling hosting packages and NOT provide reverse dns lookup???

How could any of the sites they host ever send anything to AOL? Surely AOL is not the only big server to reject mail coming from domains that cannot be looked up in reverse.

I do not know why they refuse to just do it. for me
How can they sell me a hosting package that does not allow sending email to anybody on AOL?