By the way, it's a "packet" not a "package" :)
The same happens to me sometimes. It's a repeatable problem.
When a PC is configured to wake on LAN, it MUST continue to have standby power, and network connectivity all the time. If there is a power failure, or a network outage (restarting a switch or router is enough, it acts like disconnecting the network cable from the PC's NIC), then the PC will not respond to magic packets until after being booted into Windows and gracefully shutdown again (as you mentioned you are doing).
This is a well-documented limitation in Wake on LAN. I'm not sure if this is by design, or just something that couldn't be avoided for some reason- but I can repeat the problem on my PCs too.
Try this: look at the LED corresponding to the network jack on the switch/router these Wake on LAN PCs are connected to. The light will be on when the PC is in a state where it will respond to network wake requests. Now try disconnecting and reconnecting either the power or network cable from that system for a few seconds, then reconnecting it. Now the switch's corresponding activity LED is off. So the PC's NIC is basically shutting down completely during this brief interruption. Maybe it thinks there's no point staying on, so it does this to save a fraction of a watt of power. I'm sure it's something crazy like that.
I set the BIOS in some customer PCs (where reliable remote access is critical) to "return power to ON" after power interruption. This will turn a PC on after a power failure, even if it was shutdown when the power failure occurred. A PC which is on and ready to accept remote connections is a lot better than one which is off and will not respond to wake on LAN requests- forcing someone to go to the office just to press a button.
Most people using LogMeIn to remotely support PCs who use the "Switch on" feature will have seen this a few times (it basically incorporates wake on LAN and suffers from the same problem you described).
I'm guessing what's been causing yours to stop working was momentary environmental power issues. It's hard to be sure though. Perhaps you can work it out knowing the things that cause this problem.