I am going to try connecting the relay coil between IGN (through a diode) and the 12V output of the PSU. This performs the "power on button press", but can not perform a "power off button press". So it does the job with just one relay and no capacitor. Plus, there is no timing to worry about, it will always press the button just long enough to bring the computer up.
Without the diode, the relay coil would be energized with reverse polarity once ignition went low. This would hold the button until a forced power-down occured, I think.
I apologize if somebody already proposed this. I have to admit I didn't read the entire thread.