Você precisa adicionar o endereço IP de seu (s) host (s) à lista de "retransmissores permitidos".
Aqui está um artigo simples sobre como configurar esse no Ubuntu, que tem um tipo de configuração arquivo dividido (como debian) e assim difere do oficial.
Basicamente:
you set
dc_relay_nets
underupdate-exim4.conf.conf
to the IP address of the machine you want to relay from. Then you do the split config dance and runupdate-exim4.conf
and you should now be able to relay email from that IP (or range of IPs).