the only time they won't wake, is if they had the power disconnected from them.  otherwise they wake every time for me.  You just have to make sure the Bios settings are set correctly.  it varies from motherboard to motherboard, but i haven't ran into a pc that I couldnt get to wake on lan in quite some time.

in the event that they do lose power, you can also set them to power on automatically when power is restored.  this is also a setting in the bios.