We are getting the SAME error message. We can send out to External and receive External email, we just cannot send/receive INTERNAL emails.
We get this error message in sending internal emails.
it was to do with the DNS provider as they have an upstream server issue that is not allowing DNS lookups on our Name Servers.
When I called the DNS provider support line, they knew of email issues and are working on the issue.
and they said its affecting quite a few companies that use their DNS service. its only affected emails. A-Record DNS is working fine.