Como primeiro passo eu faria uma pesquisa NS no seu servidor local do MS Exchange para o domínio da outra empresa para verificar o que você tem aqui:
nslookup
set q=mx
Eu vi algumas configurações em que eles tinham um servidor Exchange local (e, por alguns motivos), uma entrada MX local apontando para o servidor Exchange não mais existente, em vez para o da nuvem. A correção aqui foi muito fácil, pois uma limpeza de DNS resolveu a bagunça.