explorer.exe is the same as the program that browses your machine (Windows Explorer).
Before you run and reformat, try deleting your TEMP files. You might just have too many in there. That can cause this problem, because Windows needs to write files to the temp files directory while it's operating, and if that directory has too many temp files, it cannot write to the directory, and it freaks out.
Try doing these basic maintenance actions before going more drastic:
-- Delete all temp files (c:\windows\temp\*.tmp, or on XP C:\Documents and Settings\username\Local Settings\Temp)
-- Delete temporary internet files (c:\windows\temporary internet files\*.*, or on XP C:\Documents and Settings\username\Local Settings\Temporary Internet Files)
-- If you use I.E., click on Tools, Internet Options, Delete Files, select "delete all off-line content", click OK
-- Click on Start, Programs, Accessories, Systems Tools, Disk Cleanup
-- Download
AdAware, check for updates, run it and remove whatever it finds
-- Download
Diskeeper and defrag
-- Download, update and turn on
SpywareBlaster and
SpywareGuard (or your spyware removal tool of choice).