Had to do this the hard way myself... IF you're running a mail server you need the rDNS set up correctly or you'll get blacklisted.
We use Verizon FIOS from a residential address so had to set up a static IP first - which involved moving our internet access account away from our residential TV, Phone, internet package and onto a business account. Once that was done (yawn) Verizon will then ordain to set up the correct PTR record. In their case, you have to find the right department (business internet) and then email them your details, IP etc and voila 24 hours later it is done.
I'd imagine Verizon proxies most ISP's.
Interestingly, we had to keep TV and phone on a 'residential' account - because we have Electronic Program Guide and VoD on our TV - and 'business' TV accounts don't support these features.... (double yawn)!