all relevant MX records point to non-existent hosts

We have Exchange 2007 sitting on our Server 2008 DC that receives and distributes E-Mail to all users on our network.  

Our domain is registered with and our DNS record handled by DollarDNS and we use the backup MX record service provided by so that should or server go down for any reason e-mails are routed to them.  

When a major client of sends us e-mails, every now and then the e-mail will be bounced back to the sender with the message 'all relevant MX records point to non-existent hosts', but then an e-mail from them will get through.  As far as I can tell our DNS records seem to be ok, our mx record checks out ok and I am at a loss as to why these bounce backs are happening.  Could anyone help with a reason as to why this is happening or give me some other things to check?
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

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.

Alan HardistyCo-OwnerCommented:
Okay - what is your domain name?  If you post just the domain name I will hide your comment - this will allow me to give you specific advice.

Run below command to find which server is accepting the mails:
nslookup -q=mx

after getting the result of the above command, try to telnet the server and post the result of the telnet.

telnet servername 25

but be sure the post 25 must be open in your firewall. Run the telnet command from outside and inside of your network.
If you find that post 25 is blocked on your network you'll need to check Firewall rules on your side; you'll need to permit Outbound SMTP on TCP Port 25 from your mail server. Check for antivirus software on the server as well, most modern AV clients block Port 25. After all this tests post the result. Also please post the full bounce back for analysis.
Alan HardistyCo-OwnerCommented:
Okay - you have 4 MX records with priorities of 10 / 20 / 30 / 40

The ones with Priority 10 and 20 point to the same IP Address, which is pointless.  I would lose the Priority 10 MX record completely.

I can connect successfully to all IP's using telnet on port 25 - so there are no issues there.

When I connected to your own server - you are advertising yourself as server-w2008.domain.local.  Hopefully you are not configured this way on your SEND connector otherwise this will cause you mail-flow issues.

Long and the short - you don't have an MX record problems apart from the unnecessary duplicate MX record.

You do have an issue with Reverse DNS in as much as you don't have as your Reverse DNS record.  You should call your ISP and get them to change this (if they can).  This might cause you problems sending if you don't.

Protecting & Securing Your Critical Data

Considering 93 percent of companies file for bankruptcy within 12 months of a disaster that blocked access to their data for 10 days or more, planning for the worst is just smart business. Learn how Acronis Backup integrates security at every stage

simonb1975Author Commented:
I don't want to send the full bounce back as it will reveal my customer.  How much do you need?
Alan HardistyCo-OwnerCommented:
Their IP Address / Domain Name should be sufficient (I will hide it again).
Alan HardistyCo-OwnerCommented:
I don't see any problems with the headers.  It would appear to be a DNS issue with the sending relay server for the client.

Do you want me to send you a test email?  If so - where to?
simonb1975Author Commented:
send to
Alan HardistyCo-OwnerCommented:
On the way.

Alan HardistyCo-OwnerCommented:
Okay - so you received my email and you replied.

This says there is not a problem with your server (or mine) so the problems have to be with the sending server - which based on the name of the domain will be like pulling teeth trying to get them to resolve it!

Ultimately - it is out of your control.  Your end is fine.  Their end is not.

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
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.