No es la primera vez que observo que pasa y oso cuento de que va:

Muchas veces en un dominio ves todo el entorno de red en el interface gráfico y otras veces de repente te faltan equipos, esto es aún más complicado si se tienen subredes distantes separadas por Routers.
El acceso a los mismos sigue existiendo lógicamente a través de una ruta UNC que se ponga en el explorador de archivos, el ping se sigue realizando a un nombre o a una ip, pero el caso es que los equipos no los muestra, puede que incluso los de una subred si las de otra no.
Muchas aplicaciones windows en su entorno gráfico dependen de esta visibilidad de modo que si no encuentran un equipo no dan la opción de poner ip o similares, realizan una búsqueda cerrada en su aplicación.
El caso es que he encontrado esta información, aunque esté en inglés, donde habla de Netbios y NAT, aquí os lo dejo, en mi caso habrá que revisar algún router a ver si es la causa del problema:

http://www.faughnan.com/netbios.html