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 $160 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 responsibility falls on the owner of the IP address.

A lot of companies will provision lines from larger ISPs, and that is who ultimately owns the IP address. Contact the ISP and get rDNS setup and your e-mail woes will go away. A reverse DNS works just like DNS, just in reverse. When a mail server gets mail from your domain, it performs a reverse DNS to see if the mail server name matches the IP address. So just make you mail domain (i.e. mail.yourcompany.com) point back to the IP address of your mail server (either your WAN address if your nat'd or its external address if its 1-1 nat)