Verifique se todos os seus servidores usam o Controlador de Domínio para resoluções de DNS. Esse geralmente é o problema. Parece que suas máquinas estão recebendo IPs que estão sendo entregues de fora da sua rede.
Execute também ipconfig /registerdns
(com privilégios elevados) nas máquinas, se a resolução de DNS do Controlador de Domínio não corresponder.
O multihoming não deve ser um problema, acredito que a configuração padrão é se registrar no DNS para que pareça uma lista de IPs separados por vírgulas para o servidor fornecido.