It turns out it was the keyboard. Say what? Well.. I've been having this weird issue where the keyboard's lights would all be lit and windows would give some "somerandom.dll is missing" error message. When I first encountered this like two months ago, I unplugged the keyboard and replugged it and worked fine. Apparently there some known issue where keyboards can build up a charge and Windows XP will think a .dll is missing (wrongly).
So anytime I shut down my computer I'd have to boot, unplug the keyboard, replug it in after it shut itself down automatically, and then restart. Sometimes several times to get it to work. I guess the keyboard finally flaked out that last bit on the drive home and was now shutting off my power supply before booting.
I'm not exactly sure how any of this works, but replacing my keyboard with a spare and now everything works fine. Go figure.