Os computadores por trás do roteador NAT? Os computadores estão em wi-fi ou com fio? Eles têm IPs estáticos?
Uma possível causa pode ser "isolamento do cliente". A maioria dos roteadores Wi-Fi oferece suporte a "isolamento sem fio" ou "isolamento de cliente" como uma forma de recurso de segurança. Isso faz com que todos os clientes de Wi-Fi que se conectam ao roteador não vejam nenhum outro cliente na rede. Verifique se esse recurso está desativado durante o teste.
Observação: não posso comentar sua pergunta ou eu teria feito as perguntas lá. Isso ajuda a entender a rede que você tem.