Resolvi dar essa dica, pois tive esse problema em praticamente todos os servidores de e-mail que instalei até hoje.

Alguém já testou receber um e-mail do seu próprio servidor e constatou que a hora do e-mail não confere com a hora do servidor?

Testei essa solução usando o Slackware (10.0, acredito que em outras versões seja igual ou parecida).

Então lá vai a dica:

# timeconfig

Escolha a opção "America/Sao_Paulo" e depois dê um restart no sendmail:

# /etc/rc.d/rc.sendmail restart

Isso vai resolver o seu problema :)