PTR records with Windows DNS Server not working

Reverse lookup records translate IP addresses back into names. A lot of mail servers like to do this as part of anti-spam measures.

You need to request that the party authoritative for the reverse zone your email server lives in create the PTR records. That's probably your ISP. There's nothing you can do in the DNS server in your office-- the rest of the world doesn't look to that server for DNS. When the 3rd party mail servers initiate a reverse lookup request, that traffic isn't coming to your office-- it's going to ISP DNS servers.

I'd start by contacting support at your ISP.

(I'm assuming, in all of the above, that you're not the authoritative party for your reverse DNS zones, but probably just somebody hosting a mail server on the end of a point-to-point Internet connection from some random ISP.)

How are your PowerShell skills? It could be a fairly straightforward matter of using

$hosts = Get-WmiObject -ComputerName $DomainController -Namespace 'root\MicrosoftDNS' -Class MicrosoftDNS_AType 

And then using the CreateInstanceFromPropertyData method:

foreach ($record in $hosts)  {
  $PTRRecord = [wmiclass]"\\$DomainController\root\MicrosoftDNS:MicrosoftDNS_PTRType
  $PTRRecord.createInstanceFromPropertydata("foo","bar","baz")
}

My example above is an excerpted (and sanitized) bit of a script I use to add CNAME records for existing A records. Doing PTRs should be quite similar; fix my foo-bar-baz handwave. There are more ideas and pointers in this Scripting Guys article.