Not receiving mail. Senders receiving Mail delivery failed: returning message to sender

We are not receiving any external emails through our exchange server. Internal emails are received. Email was working fine until last night.  The only change I know of is our ISP was supposed to setup reverse DNS. When some one sends a mail they receive a bounce back message:
Mail delivery failed: returning message to sender
A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:
    The mail server could not deliver mail to  The account or domain may not exist, they may be blacklisted, or missing the proper dns entries.

Windows SBS 2008 with exchange 2007

Thanks for you help.
Who is Participating?
Cliff GaliherConnect With a Mentor Commented:
There you go. Missing A record with your public DNS host. Whether you host with your domain name registrar, your ISP, or aid 3rdarty. Not an internal or server problem. All public DNS.
Cliff GaliherCommented:
Not a lot to go on. Start with to get more insight to your mx and other dns records as well as more deliverability.
enfusetechAuthor Commented:
Thanks for the response. Here is the message I received.

      Testing inbound SMTP mail flow for domain
       ExRCA failed to test inbound SMTP mail flow.
      Test Steps
      Attempting to retrieve DNS MX records for domain
       One or more MX records were successfully retrieved from DNS.
      Additional Details
       MX Records Host, Preference 50
      Testing Mail Exchanger
       One or more SMTP tests failed for this Mail Exchanger.
      Test Steps
      Attempting to resolve the host name in DNS.
       The host name couldn't be resolved.
        Tell me more about this issue and how to resolve it
      Additional Details
       Host couldn't be resolved in DNS InfoDomainNonexistent.
Making Bulk Changes to Active Directory

Watch this video to see how easy it is to make mass changes to Active Directory from an external text file without using complicated scripts.

enfusetechAuthor Commented:
We use the Time Warner DNS for our network and ATT to host the website.   How would this get changed? Everything worked correctly until last night. Do I need to make a change to our domain name DNS records or did Time Warner mess something up on their end?

Thanks for the help.
Cliff GaliherCommented:
If TW exposes a DNS control panel, you may be able to fix this yourself. If not then you will need to call and work with them.
enfusetechAuthor Commented:
Thanks. Before I posted on here I spent 2 hours trying to convince them they had made a mistake. They said it was a problem with AT&T then they said it was something wrong in the Server configuration. I'll call them again.

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.