This sounds kinda vaguely like a problem we had here not long ago. Some spyware or adware installed a shim in the IP stack. Then our spyware removal tool just yanked it out, leaving a gap in the stack. We had to remove the IP driver altogether and reinstall it. The symptoms are not identical, and this was under 2000 instead of XP, but some of your symptoms sound familiar. Let me see if I can find the instructions for reinstalling IP. There were more steps than you'd think.

Edit: Here it is.