A melhor maneira seria usar o servidor Exchange como um host inteligente para enviar e-mail. Desta forma, o Exim irá se conectar ao servidor Exchange e enviar os e-mails através dele, em vez de enviá-lo diretamente para outros servidores de e-mail.
Como você está usando o Debian, você pode usar dpkg-reconfigure exim4-config
e usar a configuração do host inteligente.