“network error during host resolution”

I am running an exchange 5.5 server and all of a sudden having a problem with a few domains that have the error “network error during host resolution” coming back. I did verify the domains and emails are coming from those domains. Nothing in MS Technet that I could find. Ping/Tracert find the mail servers.