I'm guessing that when both machines start back up, they are trying to get a signal from the monitor, but only one of them will be successful, and thus why you have to restart one of your machines.
I highly recommend getting an uninterrupted power suppy (UPS) so that they don't go offline at all. The computer can take being knocked off now and then, but your chances of having hardware failure or data loss will come sooner than later. If you keep an eye out you can find them on sale for as low as $10-20. They keep ONE computer up for 10-15 mins, but you can easily tailor the software so that you tell both computers to shut down ASAP.
An alternative may be to try disabling one of the machines fromrestarting automatically after power failure (in the energy saver menu)and have it manually boot it up after the first system is done starting up. Maybe this will clear up the computer not detecting a display.