I had a similar experience with spyware recently, my brother downloaded some software from a newsgroup and ran it's activation utility. Internet explorer effectively became useless.
Now something to remember when removing spyware from your PC. ALWAYS DO IT FROM SAFE MODE! If you don't know how to get into that, reboot your PC, hold down F8 and select safe made from the boot list.
The reason for doing this is safe mode. If a file is loaded into memory, then it can't easily be removed epically if it's in use. What my spyware did, was download other spyware programs then install them. So it appeared as if the spyware I had removed had not been, this ran every time I launched internet explorer. Also these programs often start up with windows.
Most anti spyware programs are a pain in the bum, because they install, they tell you, you have spyware, then charge you to purchase the removal engine. Good business yes, annoying to the user? Hell yes.
After scowering the internet for spyware removal tools I found two that did the trick.
The first was Spybot, search and destroy. It's free, and works wonders. It will even protect your machine from being reinfected.
http://www.safer-networking.org/en/download/
The second is Malwarebyte's Anti-Malware - It is a trial version, but it will search and remove any spyware software, as Spybot is already protecting my system I didn't need to purchase it, and it did catch a few registry entries that spybot lost.
http://www.malwarebytes.org/mbam.php
So, fix proceedure:
1. Download and install both Anti-Malware, and Spybot.
2. Run Spybot, Click on Update on the left hand side, to get the latest definitions (this ensures it will catch the latest threats)
3. Select any server click continue.
4. Ensure there is a tick in each box and click download.
5. Click Exit.
6. Click on Check for problems and allow for a full scan.
7. Any problems it detects, remove.
8. Close the software.
9. Run Anti-Malware
10. Click on the Update Tab
11. Click on Check for updates, it will download and install them.
12. Click on perform full Scan.
13. Allow it to remove anything it finds, if it can't remove some things don't worry.
14. Shutdown your PC.
15. After the BIOS data screen hold down F8
16. Select Safe Mode (you don't need networking or command prompt)
17. Load Anti-Malware
18. Click on perform full scan
19. Allows any threats detected to be removed.
20. Close down the software.
21. Run Spybot.
22. Click on Check for problems and allow for a full scan.
23. Any problems it detects, remove.
24. Close software.
25. Run AVG anti-virus scan.
26. Remove any threats.
27. Reboot your PC.
28. Enjoy a spyware and virus free computer.
29. Buy a decent virus scanner, such as Norton or Macafee.
30. Don't run dodgy software, or visit nasty websites.
I hope this helps!