Format and reinstalling windows is the most drastic step you can take. You have to make sure you backup every single file that you have in My Documents, your application settings, your address book, your mail (Outlook Express), a list of program you installed... And then you have to make sure you patch it and everything else before someone decides to scan you with nmap then exploit with Metasploit. There's always a smarter step than reinstall.
Also, I'm not sure what you mean by scan explorer.exe for errors. Not sure there are "Microsoft Certified website" either. Explorer.exe loads modules, which can be dll's. These dll's might have issues that cause explorer.exe to freeze or crash, but you can't just "scan" for errors. You often need to google the name of every dll loaded, then compare your version with the latest version...
Startup freezes aren't too bad to solve. Get Hijackthis:
http://www.majorgeeks.com/download3155.html, and run it. Click "Do a system scan and save a log file". Then post that log file back here.