Exchange SMTP 5.5.0 "Not permitted to relay" - possible issues with MX record resolution

We have a member of our staff who is attempting to send e-mail to a partner organization (domain and is periodically receiving SMTP 5.5.0 bounce messages which indicate that our Exchange server is unable to relay.  After a great deal of waiting for the intermittent problem to happen again with SMTP logging enabled, it has and it comes to light that the failed relay attempts are connecting to the wrong SMTP server.

It goes like this:  the partner organization uses a web and email services company called Roar Solutions.  The actual mail servers for the domain are listed in their MX records to be: and

which appear to be part of a mail service provided by Rackspace.  In every instance where we have successfully delivered mail to the domain, it's been to one of those hosts.  However, the recently logged failure showed an SMTP session (and subsequent relay rejection) with the host  This machine is, which is the primary nameserver listed in the SOA for

It also happens to be, in addition to a nameserver:

a) the web server for
b) an SMTP server

which gels with the relay rejection when we try to deliver to the domain.

Anyway, three nameservers are listed in the SOA record for

However, is not listed in the NS records at the parent server, and while the MX records for are present on the tiger NS, there are no A records for the aforementioned mx1 and mx2 hosts.

Now, I know that when an MX record can't be resolved for a domain successfully, Exchange will fall back on the A record for the domain.  And, no surprise, the A record for is for

Therefore, my thinking goes like this:

Successful instances:

1) DNS resolves using,, or another server with the appropriate MX and A records
2) SMTP connection is made to mx1 or mx2 and the mail goes through

Failed instances:

1) DNS resolves using, which has the MX records but no A records for the MX hosts.  This NS is authoritative, so MX lookup ultimately fails.
2) Exchange falls back to the A record for,
3) tells us to buzz off, given that we're trying to relay.

This is what I have put together from the evidence available to me and my (middling) knowledge of DNS.  What I'm really looking for is a confirmation or denial of my suspicions from someone more knowledgeable about DNS than me, as the technical staff at Roar Solutions have flatly asserted that the problem is on our end and I can't agree with that assessment.  I'm really looking to prove my case to them, more than anything else.

Anyone? :-)
Who is Participating?
AkhaterConnect With a Mentor Commented:
well first let me tell you Bravo, i've rarely seen questions put up like this on ee so respects

I have followed your logic and it sounds good to me with one difference

I have used to do the test and it looks like only shows the A records for mx1 and mx2 (

whereas ( and ( fail to do so

I have also noticed that the MX records are pointing to a completely other DNS domain another search on on these same server also shows that can resolve them but and doesn't
siskindsAuthor Commented:

Thanks very much.  You're right, graphite doesn't have the A records either.  Thank you for catching that; I thought it did but I've been looking at too many DNS records recently. ;-)

Here's a quick question to do with the resolution: when the A query is done on tiger or graphite, no direct result is obtained but the A records for the global TLD servers are returned in the ADDITIONAL section of the answer.  If we query one of them for mx1 or mx2, we get the parent nameservers for, and then querying one of those parents finally gives an A record for mx1 or 2.

Now, recursive queries are disabled on tin, graphite, and tiger.  Judging from what is happening, it seems that our Exchange server is not making iterative queries back "up" the chain to get the A records; I can understand this, as those queries would add up to a fair bit of latency under certain circumstances.  Am I correct then in guessing that Exchange's default behaviour is to not perform iterative queries and just fall back on the A record as I discussed in my original post?

Do resolvers ever go back "upstream" to parent nameservers based on the records returned in the ADDITIONAL section of a response?

Anyway, that question may be a bit too broad at the end. :-)  I'm just trying to put the final shells in the proverbial arsenal.  Thanks very much again for your help, Akhater, whenever I close this question you've earned your share of the points.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.