Question : AT&T blocking e-mails, Exchange 2007, PTR records and Certificates

This is a long one to explain
We are getting 550 and 553 undeliverables from  AT&T and SBC Global e-mail accounts the past few days. I tried submitting an unblock request to : http://att.net/blocks and I get the following e-mail from AT&T
"Thank you for contacting the AT&T Postmaster.

Please contact your hosting provider and inform them of your experience.  The resources at AT&T only block IPs based on the merit of the traffic received.  This underlying issue can only be resolved by the hosting provider administrating this IP.  You are welcome to forward this message to them.

HOSTING PROVIDER: This IP has been blocked as a direct result of the traffic into AT&T resources.  Please check your server logs for anomalies, violations of your acceptable-use policy, and/or compromised servers prior to requesting removal.  Failure to correct these issues will delay the removal of your servers from our blocklist, as well as diminishing the credibility of your network security and the availability of AT&T internet resources."

So after some research I figured it was my PTR record. Now I need to explain how the Exchange server is setup.

-Exchange 2007 SP1
-Windows 2003 x64 server
-Single Exchange server
-No Edge server
-Static IP
-MX record points to "mail.global.frontbridge.com" (Which is a SPAM filtering service that forwards the mail to my Exchange box).
When I implemented Exch 07 I also was doing a domain migration so I had to give the new domain a different name so it went from "domain.com" to "domainInc.com" but external DNS still needed to use "domain.com".
-The NETBIOS name of the Exch box is "mailsvr.domaininc.com".
I figured out that I could add new "Accepted Domain" under the Hub Transport using "%[email protected]" and set it as the default Reply under the E-mail address Policy. Created my certs, setup webmail and RPC/HTTPS. Everything worked great... Till now, AT&T has *&%ed  my world.

So this is what I have tried so far&

-I had my IP provider create a PTR record on their end to "mail.domain.com" checked it and it comes out correctly  X.X.81.64.in-addr.arpa PTR mail.domain.com
Still not working&
-Changed the FQDN for the send connector to "mail.domain.com"
Started getting Ev ID: 12014 in MS Exch Transport which points to the receive connector FQDN and Send connector FQDN not matching as well as the Cert not having that FQDN.
-Disabled the Default Receive Connector and created a new one with the FQDN of mail.domain.com
-Created a new cert request  using what is described here.. http://technet.microsoft.com/en-us/library/aa998840(EXCHG.80).aspx

Get-ExchangeCertificate (Thumbprints Removed)
Services     Subject
----------      --------   -------
.....             CN=mail.domain.com, O=company, C=us
IP..S           C=US, S=CA, L=City, O=domain.com, OU=domaininc.com, CN=mail.domain.com
IP.W.        CN=mail.domain.com, OU=domaininc.com, O=domain.com, L=City, S=CA, C=US
.....            CN=owamail.domain.com, OU=domaininc.com, O=domain.com, L=City, S=CA, C=US
.....            CN=owamail, OU=domaininc.com, O=domain.com, L=City, S=CA, C=US
.....            CN=mailsvr.DOMAININC.COM, OU=domaininc.com, O=domaininc.com, L=City, S=CA, C=US
.....           CN=owamail.domain.com
.....           CN=mailsvr, OU=domaininc.com, O=domaininc.com, L=City, S=CA, C=US
.....          CN=mailsvr.domaininc.com, OU=domaininc.com, O=domaininc.com, L=City, S=CA, C=US
.....          CN=domain.domaininc.com, OU=CAS, O=domaininc, L=City, S=CA, C=US
.....          CN=domain-cert, DC=domaininc, DC=com
....S         CN=mailsvr
....S         CN=mailsvr

The first line in that Cert request is what was just added CN=mail.domain.com, O=company, C=us

Still no luck. I've restarted transport services or completely rebooted after each of these steps. The problem I believe lies with the NETBIOS name of the server. When I do send mail to my personal account the header looks like this...

Return-Path:
Received: from noehlo.host ([127.0.0.1])
      by mx-dipper.atl.sa.earthlink.net (EarthLink SMTP Server) with SMTP id 1kG34O53M3Nl36u0; Wed, 17 Sep 2008 15:52:38 -0400 (EDT)
Received: from mail.domain.com ([64.81.x.x])
      by mx-dipper.atl.sa.earthlink.net (EarthLink SMTP Server) with ESMTP id 1kG34D2V63Nl36u0
      for ; Wed, 17 Sep 2008 15:52:28 -0400 (EDT)
Received: from mailsvr.domaininc.com ([192.168.10.30]) by
 mailsvr.domaininc.com ([192.168.10.30]) with mapi; Wed, 17 Sep 2008
 12:51:42 -0700
Content-Type: multipart/mixed;
      boundary="_000_C91EF45348FBCA4DB3E8D1D8BF4BA0F6581A567654almailsvrdom_"
From: me
To: personal [email protected]

Part of it shows the correct PTR "mail.domain.com" other parts still show the server name "mailsvr.domaininc.com"

Have I painted myself into a corner? I am at a point to where I suppose I can rename the domain back to its original name since it is no longer attached to the old forest. Is this as complicated as I'm making it or is there a simpler solution? I think with a MX record pointing to "mail.global.frontbridge.com" and internal and external names being different AT&T's changes have created a mess for me as well as myself.

Any assistance is much appreciated

Cheers

Answer : AT&T blocking e-mails, Exchange 2007, PTR records and Certificates

I think you are overthinking this. Your IP is blocked by AT&T. I'm not saying your configuration is 100% correct ...I'm just saying that that has nothing to do with AT&T blocking your IP address right now. You need to check your IP address for your outgoing SMTP server with the know spam lists. I use dnsstuff.com for this. They have a tool for Spam Database Lookup. That will tell you if your sending IP address is on any of the major lists (approx 100 or so lists). From there you can begin to decipher how you got on the list.

I have a DNSstuff account so I can run the search if I have your ip address.

This is assuming your are using your own smtp server for outgoing and not using a Smart Host.