Adding a PTR reverse record to your IP/domain is good to prevent your mails to be treated as SPAM by Google, Yahoo etc.

Check whether you have PTR record

From linux command line, execute:

dig -x yourserveriphere

BAD
dig -x yourserveripthere

; <<>> DiG 9.3.6-P1-RedHat-9.3.6-20.P1.el5_8.6 <<>> -x yourserveripthere
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 20009
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0


;; QUESTION SECTION:
;yourserveripreversedthere.in-addr.arpa. IN PTR


;; AUTHORITY SECTION:
yourparentserveripthere.in-addr.arpa. 1404 IN SOA dns100.ovh.net. tech.ovh.net. 20 13083000 43200 4320 2419200 86400
GOOD
dig -x 37.59.228.66

; <<>> DiG 9.3.6-P1-RedHat-9.3.6-20.P1.el5_8.6 <<>> -x yourserveripthere
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 63704
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0


;; QUESTION SECTION:
;yourserverreversedipthere.in-addr.arpa. IN PTR


;; ANSWER SECTION:
yourserverreversedipthere.in-addr.arpa. 21600 IN PTR ns1.yourdomain.com.
So there must be an answer section where your reverse IP points in PTR to your nameserver. If it dont points, then you must ask your IP address provider to add your nameserver (ns1.yourdomain.com) to your server IP address.

Here you can check whether your PTR and other nameserver settings are correct:
http://www.intodns.com/yourdomainnamehere.com

BAD
Reverse MX A records (PTR) ERROR: No reverse DNS (PTR) entries. The problem MX records are:
yourserveripreversed.in-addr.arpa -> no reverse (PTR) detected
You should contact your ISP and ask him to add a PTR record for your ips
GOOD
Reverse MX A records (PTR) Your reverse (PTR) record:
yourserveripreversed.in-addr.arpa -> ns1.yourdomainname.com
You have reverse (PTR) records for all your IPs, that is a good thing.
How to add PTR record?

First, make sure you added (you already have) this record in your DNS zone file for your domain. If you have Kloxo (free hosting control panel), go to / Domains / Your Domain name/ and then find "DNS" icon (Manage DNS). Or if you have another control panel, find DNS Zone section for your domain. If you have plain linux, then you can lookup zone files in /var/named

ns1.yourdomainname.com. IN A 12.34.56.78

(12.34.56.78 replace by your server IP)
(ns1.yourdomainname.com replace by your nameserver)
Then restart DNS (named) service from SSH (putty) or from "Command center" from Kloxo by command:

service named restart

Second, your server/hosting IP provider should now add reverse entry/record for your IP... Contact him if you cant see reverse IP setting in your control panel.

For example i have OVH server and i did it in OVH Manager, Server, Tools, Reverse IPv4.
I added: ns1.yourdomainname.com for my IP address. THis is so called PTR record.

--------

You can also Veriffy PTR exist using above mentioned command dig -x yourserveriphere or using intodns.com as mentioned above (see screenshots). PTR propagation may not be instant.