We migrated our ISA Server 2004 to new hardware last week. A couple of days ago, our outbound mail ceased to leave our Exchange Server and is queued with the error message "SMTP cannot connect to any DNS server."
I ran DNSDIAG on my exchange server, testing different mail domains, with total success. Nevertheless nslookup and telnet through port 25 to these domains fail.
We are not listed on any spam list.