Existem algumas possibilidades -
Os computadores modernos têm diferentes níveis de estados desligados ( sleep states ) - é possível que, com o passar do tempo, o seu computador esteja entrando em estados de hibernação mais profundos e desativando sua placa de rede - caso em que você pode ser capaz de tweek na BIOS.
O outro - do seu post, muito menos provável, a possibilidade pode estar relacionada a como você está enviando o pacote WOL - é que o WOL só funciona na rede local ou através de um agente - não pode trabalhar diretamente através da Internet mais ampla. Assim, NAT não tem nada a ver com o estado, mas pode implicar acessá-lo da Internet mais ampla.