People ask this all the time and noone ever wants to offer an answer. I had to ask on several forums and even then only 1 thing helped me get it going, and that was a manual edit of the files in question.
1. First of all you HAVE to have reverse authority for your IPs. If you do not then it is handled by your hosting company and you will need to find where in ther tech support you can ask for PTR (Reverse records) to be entered.
2. Very few hosts will assign you RDNS authority but if one does all I can do for now is point you to an excellent tutorial I found at
www.xircd.net . I was able to follow the tutorial and figure things out, cPanel is just a little different than normal but nothing that cant be figured out.
3. As you go through it, don't be impatient, it can take a while for records to propogate. Use the various online DNS checking applications to test your DNS, they can tell you when the malfunction is actually your domain registrars fault when they are telling you its your own.
4. I'll consider making an easy to follow how-to when I get more time, its really not all that difficult. The good news is if u do have RDNS authority, once its all set up and working you can create a PTR record and have it show up immediately, (at least in my case). This comes in handy to prove to various entities that they need to fix things on thier end.
Good Luck