Wow, if that didn't work, I'm not sure...
I know a lot of spyware will run in the background, watching to make sure the hijacks and garbage stay in place. If you remove the hijack without killing the app itself, it'll go in and undo any changes you've made. It's kind of odd that Spybot and Adaware didn't catch it, though.
Hit Ctrl-Alt-Del and pop open the Task Manager. Go to the Processes tab and look through the list for anything that looks suspicious. You should be able to Google the name of the process and get a pretty good idea of whether it's supposed to be there or not. Or if you want, post the list here and I can take a look at it.
If you find the culprit, you can kill the process, and then go and delete the file that spawns it. Then you should be able to reclaim your computer.
And seriously, consider using Firefox. It's pretty much 100% immune to this kind of crap.