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_netsunderupdate-exim4.conf.confto the IP address of the machine you want to relay from. Then you do the split config dance and runupdate-exim4.confand you should now be able to relay email from that IP (or range of IPs).