this sounds like a virus, if not you are all installing something that corrupts the explorer.exe among other things. if you can try a on-line virus scan. i am not sure if you will be able to run the online from the problems you describe, but it's worth a shot.
http://www.pandasoftware.com/actives..._principal.htm
i have had several computers come in with the problems you describe, i have tryied disinfecting the drives and saving the info on them but xp did not survive the procedure. i was able to backup the files, and secure erase the drive,partition/format/reinstall and all was fine. i removed viruses from them i could find no info on, or very little. several varients of each were present on all the computers i worked on. stubby, downloader turown, downloader istbar,downloader.dyfica,backdoor.v.b.9.n
they were all very hard to remove. some of the computers were not able to boot at all, others did what you describe. norton would not detect several of the ones listed above, f-secure,avg, and panda on-line scan did the best at removing them.