Good question. In most of our environments we have somebody go on site to physically power the boxes back on (or have the "power user" in the office do it for us). Geography might make that a little impractical though.
In your situation:
Hosts: VMWare KB link you posted, and then set the BIOS to "power on" after power loss and not "previous state" or "remain off". From the POV of the BIOS, even if the box was gracefully shut down, it can still tell that it lost power outside of its control (when the UPS runs out of juice), so the moment power is restored the BIOS will sense that and send a startup signal.