Keep in mind that just because the system is not "on" does not mean the components are not powered. Many systems leave the NIC powered, and some leave onboard modems powered, so the system can do wake-on-LAN or wake-on-ring startups. Some even do wake-on-key (a nod to the Macintosh!) and I've even seen a few with wake-on-clock options.
For the SME server, small UPS units are cheap. Install one and configure the BIOS to power on when power is restored.
For workstations, you could do the same; however, if the workstations are WOL compatible, then write a small script to do the WOL probes when the server is restarting. Then you can bring the entire network back up automatically.
Scott