Question : server says email domain does not exist, but it does

Various emails from our domain are getting rejected by certain clients. The message back from the other domain's mail server is:

The following message to om> was undeliverable.
The reason for the problem:
5.1.2 - Bad destination host 'DNS Hard Error looking up ourdomainname.com (MX):  NXDomain'

Now obviously our domain does exist. Whenever I check the DNS with dig from any of a dozen machines I have access to, the correct records are returned immediately. Any idea what could be going wrong here? The domain is hosted with domainbank.com, I had a thought that maybe they were having trouble?

Answer : server says email domain does not exist, but it does

The error clearly states a resolving name problem, its one of this 3 options:

1 - The person that sent the email typed the domain wrongly, try to check it closely, maybe double dots etc.
2 - The DNS that the remote mail server is using is having trouble to resolve names, if you can contact their admin, ask them to try to resolve the MX for your domain there when it happens.
3 - Your DNS servers are having trouble.

If you can paste the full error with real names i can try to check it externally.

Hope it helps you to find the problem.