Eu também tive isso. Demorei um pouco para descobrir, mas a solução que encontrei foi simples.
Você tem um smarthost que deseja usar para enviar e-mails de seu host local, que também executa o Exim4. Por esse motivo, parece que você selecionou as opções corretas do dpkg-configure exim4-reconfigure . Como seu exim4.conf.conf mostra uma entrada em dc_relay_domains. Até agora tudo bem.
Mas se o smarthost for um servidor de e-mail bem configurado, ele ainda aceitará e-mails apenas para seu próprio domínio e retornará um retransmissão não permitida de erro . Esse parece ser o caso como você descreve. Isso ocorre porque o smarthost aceita apenas emails para seu próprio domínio em tentativas de entrega de entrega SMTP não identificada. Caso contrário, seria um ponto de entrada do spam ser um chamado retransmissor aberto. Relés abertos não são bons.
Usando o smarthost, seu Exim4 local precisa efetuar login no smarthost usando uma conta de usuário e credenciais existentes. Dessa forma, o Exim4 local se identifica com o smarthost como um usuário permitido que recebe acesso irrestrito, que inclui a entrega e retransmissão de emails para domínios estrangeiros.
Para isso você precisa de uma conta de usuário no smarthost e editar o arquivo de configuração /etc/exim4/passwd.client adicionando a seguinte linha
mycompanyemail.com: [usuário]: [senha]
Isso deve fazer o trabalho. Apenas certifique-se de que a URL smarthost seja idêntica ou corresponda à entrada dc_relay_domains em exim4.conf.conf. (cadeias curinga são permitidas)
Não se esqueça de chmod 640 o passwd.client, pois contém credenciais de usuário em texto puro.