O servidor é baseado em PHP Linux ou Windows? Por enquanto eu vou assumir que é baseado em Linux. Alguns dos conselhos abaixo são válidos, independentemente, você só tem que ter uma abordagem ligeiramente diferente.
A primeira coisa a fazer é determinar se os e-mails estão chegando ao seu servidor Exchange. Quando você faz o ping no domínio, você está recebendo o endereço IP que você espera?
O email de saída deve ter um cabeçalho "Return-Path". Se o email estiver sendo rejeitado pelo Exchange, você deverá obter uma resposta para o endereço em "Return-Path" indicando por que o email foi rejeitado. Normalmente, as respostas de retorno do sendmail acabam em / var / mail.
Com a função de email do PHP, há algumas coisas que você deve ter em mente. Você está configurando um cabeçalho "De:"? O endereço é acessível? Se você estiver definindo cabeçalhos (deve pelo menos definir De :), certifique-se de não ter nenhuma linha final após os cabeçalhos. Alguns servidores de email não gostam disso.
A última coisa a verificar é o endereço IP de saída nos cabeçalhos de email. Às vezes, o sendmail coloca 127.0.0.1 em vez do endereço IP público. Isso causou problemas para mim no passado. Como o sendmail era difícil de configurar, acabei usando o postfix.
Outra coisa a considerar é que, em vez de enviar e-mails do servidor local na caixa PHP, você pode tentar configurar o PHP para usar seu servidor Exchange para enviar e-mails.