Acho que resolvi o problema. O usuário usado para enviar e-mail não era confiável, conforme explicado na página man do exim, na opção -f.
Então eu adicionei a linha no exim.conf:
trusted_users = [local user to be trusted]
Isso resolveu meu problema. Espero que isso possa ajudar alguém.