Relay Access Denied SBS 2003

Ok, this is driving me crazy still not sure how to deal with this...

This is the error we are getting from bounced back mail only from sites like AOL, Yahoo, Hotmail, etc:
 You do not have permission to send to this recipient.  For assistance, contact your system administrator.
 < #5.7.1 smtp;554 5.7.1 <>: Relay access denied>

We had recently done a few things that started this problem.  The first thing was we changed our ISP , the second we change out our firewall (sonicwall tz210).  

We instructed our ISP to point to our domain (PTR record).  That was done and no issue there.

When we run  the mail server test and enter at we are  getting "Warning - Reverse DNS does not match SMTP Banner"  and the banner is  stating: 220 ESMTP SonicWALL .

We run the Antispam service on the sonicwall and from what Sonicwall is telling me, that banner is provided per that service.

So for testing, I disabled the antispam service, and tried the mxtoolbox test again.

This time the banner is okay, displays our server and no errors.
The banner reads something like this :220 Microsoft ESMTP MAIL Service

So after that gave me the green light,  I tried sending several test emails to a hotmail account, and I am still getting the relay bounce back errors!

I checked with our ISP and they said, everything is resolving and there is nothing else for them to do and sonicwall is stating the router is behaving the way it should.

Any ideas as to what I'm missing?
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:
Reverse DNS does not match SMTP banner is your problem, and it's your answer, funnily enough.

Your IP address x.x.x.x has a reverse DNS listing on it, likely from your ISP, of

But when your Sonicwall answers the incoming knock at it's door for mail anti-spam service, it answers with, which is nothing like and the whole internet gets confused that you're not answering how it expects you to.

Get the Sonicwall to start answering with, or even maybe just and your problem goes away.
MikejettAuthor Commented:
I had disabled the anti-spam service on the sonicwall.  Once I done that everything check out on mxtoolbox.  I then tried to send several emails out to hotmail and I still got the bounce backs. Here is what I get when I run the email server test at mxtoolbox:

220 Microsoft ESMTP MAIL Service, Version: 6.0.3790.4675 ready at Thu, 3 Oct 2013 08:30:54 -0700
      Test       Result       
      SMTP TLS       Warning - Does not support TLS.        More Info
      SMTP Reverse Banner Check       OK - resolves to
      SMTP Reverse DNS Mismatch       OK - Reverse DNS matches SMTP Banner       
      SMTP Connection Time       0.718 seconds - Good on Connection time       
      SMTP Open Relay       OK - Not an open relay.       
      SMTP Transaction Time       2.761 seconds - Good on Transaction Time
Nathan PSystems ArchitectCommented:
You said you sent 'OUT' to hotmail.
Does your outbound path differ to your inbound path that you are testing?
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

MikejettAuthor Commented:
What tools can I use to check that?
MikejettAuthor Commented:
When I do an MX check on, I get this:

Pref       Hostname       IP Address       TTL       
1      36 hrs       Blacklist Check      SMTP Test
21       36 hrs       Blacklist Check      SMTP Test

This is how it has always been set up since day one.
Nathan PSystems ArchitectCommented:
That might be it too!

Pref 1 is the highest.  Hotmail connects to first, before it connects to

In fact, it will only ever try if the higher priority MX is down and unavailable/unresponsive.

You can have two MX's the same priority if you want load balancing, but if you want your server answering first, you need it at the 'highest' priority, which is the number closest to 0.
MikejettAuthor Commented:
Well I just had the parcom connectors removed so the mx only points to and I still can't email to hotmail (or others) without a bounce back.  

What else can I do to take care of this?
Nathan PSystems ArchitectCommented:
MX record edits can take time, up to your DNS record 'TTL'. Check your TTL and check again with hotmail after that much time has expired.

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:
Still not working.  I don't get it..
Nathan PSystems ArchitectCommented:
Short of giving someone your actual domain details to help them help you further, you might want to try to contact Hotmail themselves and ask them for their error code or reasoning as to why you are being rejected.
MikejettAuthor Commented:
Ok, oddly enough, it works now.  I disabled the anti-spam service in sonicwall, sent an email, and it went through.  

I then re-enabled the anti-spam service, sent an email, and it went through as well.  I don't get it, I tried this once before and it didn't work, but now for whatever reason it works.
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
Microsoft Legacy OS

From novice to tech pro — start learning today.