Eu começaria certificando-se de que as configurações são as mesmas em todos os computadores (tenho que descartá-las) ... então em cada máquina, clique com o botão direito nas configurações da interface de rede e faça propriedades, clique duas vezes em IPv4 e depois avançado.
A partir daqui, clico no separador DNS e adiciono manualmente o servidor na lista superior e, em seguida, seleciono a opção "Anexar estes sufixos DNS (por ordem):" e escolha algo como .local ou .mynetwork e marque duas opções abaixo.
Reinicie todas as máquinas depois de fazer essas alterações e vá para o prompt de comando e digite ipconfig /renew
seguido por ipconfig /registerdns
Em seguida, no prompt de comando, digite "Nslookup" e tente o nome de uma ou duas máquinas e veja o que acontece.
Se você ainda não está conseguindo onde, verifique as configurações de DNS no roteador, parece que não está permitindo que outras máquinas se registrem / é um servidor DNS de cache para a internet SOMENTE, se funcionar - legal.
Se isso não ajudar, talvez seja melhor usar apenas arquivos de hosts ou usar um firmware diferente - mas, espero que tenha ajudado.
Editar - Além disso, apenas pensei - Lembre-se de verificar se o eco do ICMP é permitido no Firewall do Windows!