Você verificou a zona de pesquisa inversa do seu servidor DNS em busca da presença de registro PTR para o servidor Exchange? Na ausência deste registro, a autorização pode não passar. Quando você se juntou ao seu servidor via DHCP, o registro PTR, provavelmente, foi criado automaticamente.