Eu acredito que esse comportamento é por design como NetBIOS trabalha com pacotes de difusão. Configurar um servidor WINS quando você configura o controlador de domínio (e habilitar o serviço de navegador de computador se for Win2k8) e apontar clientes para esse servidor WINS deve resolver isso (supondo que você tenha o roteamento configurado corretamente).
O WINS não substitui o NetBIOS, mas fornece um ponto central para a resolução de nomes de NetBIOS que pode funcionar em sub-redes.