Oooh.. Ya know what.. Two months ago, I had a problem just like this. Damned if it wasn't The Button. The power button on the front of the computer had become unreliable. There's a small chance that this is your problem.
Basically, that button connects to a couple of pins on the MB. They are often unlabeled but may be labeled as SW (for power switch). Often, the connector that goes to those pins is labeled, even if the MB is not.
Basically, the MB gets power all the time. But it only turns on when those pins are temporarily shorted. Short them again, and it turns off.
I have yet to replace the button. There is just something about sticking a screwdriver into the case and shorting the pins to start that PC that appeals to my unsatisfied car thief tendencies.