Reverse DNS does not match SMTP Banner

We have SBS  2003, I just switched our ISP provider.  We can send and receive mail for the most part with the exception of sites like hotmail, yahoo, etc.

 We get the error: you do not have permission to send to this recipient.  For assistance, contact your system administrator.
            < #5.7.1 smtp;550 5.7.1 <>... Relaying denied. Proper authentication required.>

For example, we have our setup up is like this:

 FQDN setup as:
 MX record is: pointing to
 PRT is: pointing to

When i test on the mxtoolbox site, I get this:   SMTP Reverse DNS Mismatch       Warning - Reverse DNS does not match SMTP Banner.

Obviously is the new IP address I had changed.  What else am I missing here that I am getting the relaying errors?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Nathan PSystems ArchitectCommented:
Contact your new ISP, have them set up a Reverse DNS for your new IP address that matches the service you are listing.. in your example

They own the IP space, so you have to go through them, but they need to be telling the internet that to their knowledge, exists there, so that you are trusted enough to send mail out of there.

I hope this helps.
Nick RhodeIT DirectorCommented:
As LectricX posted, contact you ISP and advise them to update their records.  It can take up to 24hrs for it to be updated completely.
MikejettAuthor Commented:
If my  A record is and the PRT record is

Is the prefex here the issue?
Nathan PSystems ArchitectCommented:
No.  Your DNS servers have no control at all over REVERSE DNS listings.

It's like this..   DNS is you giving out your business card to people you meet.   You get to advertise your name and number (url and IP address) to whomever asks...

Reverse DNS is like the phone company publishing your telephone number in the phone book.  YOU have no control over what they publish, and you cant change it, but you can call the phone company and ask them to change it for you.. right?

Reverse DNS changes MUST go through the owner of the IP address space, and as mentioned before, this is likely your new ISP.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
MikejettAuthor Commented:
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.