PTR Record Help, Reverse DNS Settings

Okay i have a client vps having trouble sending email.. certain domains are blocking them from what i can tell because no/invalid PTR records

Here is my setup

I have my business domain on its own VPS running Plesk11 with 2 ip addresses for private nameservers, in the dns i also have two more nameservers pointing to another server that i put clients on

Server 1 - company.com (me)
IP 111.111.111.111 ns1.company.com
IP 222.222.222.222 ns2.company.com

Server 2 - Client Server ns3.company.com
IP 333.333.333.333 ns3.company.com
IP 444.444.444.444 ns4.company.com


server 1 has all the proper private nameserver settings to point to the client server correctly.  So if a client points their domain to ns3 and ns4 everything works fine.

On the client server everything really defaults to ns3.company.com.  If i run a ptr checker http://emailtalk.org/PTR.aspx  for the ip or domain of ns3.company.com it says no ptr record found.

So i guess my issue is how to properly configure this, do i put the PTR on the main server? or the client server? (because i do have a default domain of ns3.company.com on the client server)

and then what should the PTR be? Im confused.  I put a PTR for the ip of ns3 on the main server dns (me) for that ip address and waited a couple days.. but still nothing

here is the email error clients are getting:

72.167.238.201 failed on DATA command.
Remote host said: 550 5.7.1 SPF unauthorized mail is prohibited.

another:

66.133.129.79 does not like recipient.
Remote host said: 550 #5.7.1 Your access to submit messages to this e-mail system has been rejected.
Giving up on 66.133.129.79.

Please help

Thanks