É difícil obter uma boa resposta se você não está definindo o problema claramente: como você sabe se eles estão na mesma LAN? Mesmo switch, mesma sub-rede, mesmo edifício físico?
Verificar a sub-rede deve resolver a maioria das situações.
Outra abordagem (se os dois PCs estiverem "conversando" um com o outro) é verificar a tabela ARP para ver se o IP está lá: arp -a do prompt de comando. Isso significa que você tem conectividade com a Camada 2.