Entendi. O serviço Pesquisador de Computadores estava desativado por padrão no Windows Server 2012 Essentials. Não tenho certeza porque mostrou alguns computadores e não outros. Mas de qualquer forma, eu também libertei o cache do arp e parece estar funcionando agora