Erros como esses geralmente são problemas relacionados à resolução de DNS.
Tente executar o nslookup localmente no seu servidor Exchange:
set type=mx
gmail.com
Veja os resultados (execute a consulta gmail.com várias vezes) e veja se permanece coerente. Verifique com um cliente externo em relação a um servidor DNS diferente e veja se ele corresponde.