Of course nothing cleans a computer better than a clean installation of the OS. If in doubt, a zero fill or some other wiping method will destroy any nasties that might self-recover from a normally formatted disk. There are some things you might want to try, though, if you'd like to check for some files to save through the original OS.
If you have the XP installing CD or the Recovery Console installed, you could also either run chkdsk /r, extract/expand explorer.exe or do a full repair install. I'd try with chkdsk first and if it wouldn't do the trick, do a repair install. You never know if there's some other file missing, too.
You also said you had run Anti-Malware the previous day with no finds. That doesn't mean you couldn't have a nasty MBR virus or rootkit in your computer, in which case all the above is in vain. So the
very first thing to do would be running a rootkit finding virus scan from a CD. I have used
F-Secure Rescue CD for that purpose with good results. Just make sure it can download updates, not all network cards are supported. It can also be updated with a USB stick.
There's also the possibility of bad sectors in the hard disk drive. Most manufacturers have testing programs for that, or you can get a collection of them on
Ultimate Boot CD.
There's always a reason for a system file to disappear. IMHO it pays to find it out: Installing on a faulty disk can fail during the installation, making file rescue hard if not impossible. Installing on a heavily polluted disk without wiping can cause the new installation to be infected from the start.
Oh, and how can a computer be "clean" before shutting down and polluted the next startup? Here's an educated guess: One gets a piece of malicious code, which doesn't activate until the last seconds before shutdown. The antivirus program might already be down, and the code tries to infect an essential system file or driver like explorer, or the mouse/keyboard/display driver right before shutdown. If it succeeds, the virus code would act as a part of your running OS, making it impossible for your antivirus to eliminate or even find. The infectation has to happen in nanoseconds, among other possibilities of failure, which can lead to an unstable or non booting system.
