So it's working for several years, until a few months ago, when it starts shutting off about 1 minute after boot. It didn't seem to be an overheating issue, so I thought it was a power supply thing. After a little undusting, though, the problem went away.
Then, it came back. Since undusting worked so well the last time, I tried it again. However, it didn't work, and while I was fiddling with the insides of my computer, a lithium battery fell to the bottom, like, the kind that powers your BIOS. After this happened, when I booted up, the BIOS wouldn't show (in fact, nothing showed, while previously, startup would proceed as normal until it randomly turned off).
Well, that's natural, right? I just went to put the battery back where it had come from... but I didn't know where it came from. There is only one slot for the circular CR2032 battery on my motherboard, and there was already a battery lying there. I of course tried switching them, and all, but that didn't help.
So now, I'm puzzled as to where this battery came from (inside my graphics card? I can't open it...) since there doesn't seem to be anywhere it fits.
There should only be one battery on your motherboard. And the graphics card doesn't contain a battery. Unless you have other devices not mentioned attached to your system that require a coin battery, I have no idea where it could have come from. But there's a good chance it may have been shorting some delicate circuits on the board or other equipment that caused your failure.
Before I found the coin battery at the bottom of my case (i.e. at the beginning of the dusting), my computer would start up as normal (and reach the OS) before shutting down, but after I found it, it wouldn't even go to BIOS.
The battery incident might not have been directly related to the change (but it does seem likely)... are the symptoms typical of a failing power supply? Fried motherboard?
After a period of time of being frustrated, I bought a new power supply (Corsair CX 600W) and a new graphics card (GeForce GTX 550Ti) and installed them.
My current symptoms are "computer turns on, then does not show a display, does not turn itself off". I have reset the bios both by removing the battery and by the jumper. These symptoms occur with both my old graphics card and my new. I've reseated just about everything I can find. The only thing I can think of at this point is that my motherboard is just plain dead.
Without being able to do a thorough troubleshooting myself, my first 'guess' is as stated above. That the errant coin battery grounded out or shorted some circuitry on the motherboard. It may have been in a safe spot until you moved it during cleaning. If that's the case, you may need to replace the board.
If you feel up to the task and you want to be a little more sure the problem is board-related, you could remove the board and place it on an insulated surface. Connect just a single stick of RAM, the CPU/HSF, PSU power, and one of your video cards* known to be good. No drives, etc. Connect the monitor to the video card and power up the system by shorting the two pins the power switch would connect to. See if you get a display and can enter BIOS. If not, I would say the board is bad.
If you're nervous about shorting the two pins, maybe you can set the board close enough to the case for the power switch wires to reach those pins, and use the case swititch to start the system.
*(being an X58 board I'm presuming you have no integrated video. Otherwise I'd say leave the card out and connect to the integrated video.)