Existem várias razões para isto, desde problema de rede, bloqueios, a configurações do servidor de email. No caso, iremos tratar de uma falha causada por problemas de DNS somado a configuração do Exim.
Não iremos apresentar a melhor forma de solucionar o problema, que seria corrigir o motivo pelo qual a configuração está falhando. Iremos apenas apresentar uma solução rápida para quem precisa resolver a coisa, fazer funcionar o quanto antes, para depois poder entender qual o motivo deste delay na conexão externa.
Em geral os testes na rede interna na conexão costumam funcionar perfeitamente. Mas toda tentativa de rede externa falha ou demora de 20 a 40 por exemplo.
Vá na configuração correspondente do seu exim e procure por dc_minimaldns que provavelmente estará com o valor ‘false’. Caso esteja, nossa dica tende a servir para você corrigir emergencialmente este problema de demora.
Basta mudar para ‘true’, ficando dc_minimaldns=’true’.
No caso do Debian, com Exim4 e arquivos de configurações separados, esta configuração pode ficar no arquivos /etc/exim4/update-exim4.conf.conf