well the problem could be that one of these wonderful spyware apps depend on exploder being the shell. We have found in the past that many programs out there like to cut corners using parts of the explorer shell thinking "why would anyone not want explorer?"

As for removing of the stuff...most commonly you will find that these apps dig so deep that you can't remove them. Normally you will find a .reg file here or there that reloads it back into memory, or you will have some open exploit on your machine that you keep getting infected through. Good luck on killing them off though.