Verifique se a sua configuração de DNS está correta (todos os servidores listados em /etc/resolv.conf estão ativos e respondendo rapidamente). Grandes atrasos no envio de e-mail geralmente significam problemas de DNS.
Temos um VPS executando o Postfix 2.3.3 no Centos 5.3, e parece demorar muito para enviar um e-mail.
Há um aplicativo em execução no servidor (drupal) que envia uma série de e-mails ao enviar um formulário, e parece que está demorando muito para enviá-los - como de 30 a 1 minuto para cada um. Até mesmo disparar mail da linha de comando tem uma lentidão similar.
Se eu tail -f /var/log/maillog conseguir ver todos os emails passarem, haverá uma grande pausa antes do primeiro e entre cada email subsequente.
Eu tenho apenas a mais vaga compreensão do que estou fazendo aqui, então não tenho certeza de que outras informações que eu possa fornecer podem ser úteis. Tanto quanto eu sei, nós apenas temos uma instalação padrão de centos, postfix e webmin em execução.
Qualquer sugestão sobre onde procurar e o que fazer enquanto eu estiver olhando seria muito apreciada.
Sim, eu concordo com womble. Tente configurar o dns na máquina do servidor de e-mail local e liste a máquina local como um servidor de nomes no /etc/resolv.conf.Pode resolver o problema.