Eu decidi desinstalar o sendmail e instalar o postfix.
Por alguma razão, a desinstalação do sendmail não para o MTA, então corra
ps aux | grep mail
e elimine o processo manualmente. O postfix funciona bem direto da caixa.
editar:
Além disso, para evitar a entrega local (a menos que você realmente entregue e-mails do servidor usando pop, etc), em main.cf apenas se livre da referência do nome de domínio. Funciona como um encanto.
Outro benefício do comando Postfix: mailq mostra retornos e respostas do servidor se eles negarem a mensagem. Eu nunca consegui descobrir isso com o sendmail, mas com o postfix o mailq é muito útil.