I usually have to format a few times a year...
To redo the system when a rebuild won't fix it, just reinstall Windows OVER itself and then go make sure all of your patches and updates are still functioning at the ms updates. We have one system that hasn't been redone in almost 5 yrs and it runs like a top. (did the reinstall thing twice)
Doesn't XP have the rebuild thing JUST for IE? Go to remove programs, choose MS Internet Explorer and it should bring up that option to remove or rebuild.