first get a copy of Spy Sweeper from this link:
http://downloads-zdnet.com.com/3000-2144-10200144.html
and run it on that computer (even the trail version works perfectly)
Then you search the registry for the name that pops up on your IE and remove the entry for it... what happens is, basically these fake search managed to tag an extension of their URL to the IE setting in the registry and that's how they get around it.
cheers