Verifique seu sendmail.mc se FEATURE(require_rdns) estiver ativado. Se não verificar também se o seu binário sendmail é compilado com suporte a tcp_wrappers, e se sim, verifique as políticas (específicas para sendmail, ou padrão se ausente para sendmail) em /etc/hosts.allow e /etc/hosts.deny
ATUALIZAÇÃO:
Existem mais alguns arquivos para verificar. Primeiro, verifique /etc/nsswitch.conf (ou /etc/mail/service.switch ), se existir. Entradas normais para resolução de DNS são:
hosts: files bind
Em seguida, verifique as entradas de /etc/resolv.conf . Os servidores de nomes listados estão respondendo? Talvez o primeiro não esteja acessível e essa seja a causa dos atrasos.