Are these machines all the same make/model or are they different? If all the same, are they running the same BIOS version, and is WOL enabled?
I do recall faultfinding some old machines where WOL was not working although I could pick up the WOL "pulse" generated by the NIC. It appeared that the pulse was not switching the PSU on. This proved to be a hardware issue. For WOL to work, the NIC chipset needs to have power available to it all the time, and the standard AT PSU should be providing a 5V low current supply even when the machine is powered down. This ensures that the NIC chipset can respond to a WOL packet, and generate the switch on pulse that turns on the main part of the PSU.
So do not exclude the possibility that there is a hardware issue, either with the ports that are servicing the failing machines, or with the machines themselves. If the machines have been switched off at the wall then they will not respond to a WOL packet so make sure the cleaner is not messing with the sockets when plugging in the vacuum cleaner (yes - old joke but it does happen).