Lavasoft Ad-Aware is quite good for removing spyware. If it doesn't work or you don't want to use it, try the following: I would load up the Task Manager (right click on the Task Bar and click Task Manager) and go to the processes tab. One of the processes will be the spyware. But which one? Try Googling some of the more suspicious-looking process names (most, like iexplore.exe, will be completely innocent). When you think you've identified the process causing the problem, search for its location on your hard drive and delete it. Before you delete it, you'll have to end the process in Task Manager by click on "End Process".
Please note, this is a reasonably risky process if you're not sure which process to delete! So be careful if you try this.
Another option is to back up all of your personal data onto external media and use your XP disc to wipe your hard drive and reinstall Windows. Sounds pretty drastic, but you get a very fast, shiny new PC out of it. I do it fairly regularly just to keep my computer as fast as possible.