Don't feel bad, I've had the SAME exact thing happen at my work on my work PC and they had to fix me up.

I'm not sure what Adware/Spyware software that they used, but they had to run it over and over again. Finally, after like the 5th time, they removed ad/spyware from my machine and went in through the 'control panel' and made changes to internet options by changing my home page back to what it was "google", deleted all my cookies and cleared out my temp internet history files.

One other thing that they did was to delete everything in cache.

Try all those things right after running your spyware software and then do the rest (empty cache and change home page) before you even invoke internet explorer ( do not invoke internet explorer to get to your internet options...go through control panel).

I'm not certain any of this will work....just letting you know what all I noticed when my helpdesk folks fixed my VERY similar problem.