Para sanar isto tenha certeza de alguns pontos:
1 – que a zona de dns tem um mx configurado LOCALMENTE,
2 – este tutorial foi executado no debian 5,
3 – este tutorial usou exim-heavy.
No arquivo /etc/exim4/update-exim4.conf.conf tenha certeza de que a linha linha abaixo terá a configuração que mostrarei:
dc_relay_nets=’127.0.0.1;IP_REAL_de_Pessoa_externa_tentando_enviar;IP_REAL’
Separe os ips por vírgula caso necessite de ips os quais são EXTERNOS, ou seja, pessoas conectando apra enviar emails.