It hides in the registry as a BHO (browser helper object) and as long as it's there it will give you grief.
Just follow the instructions with Hijackthis.exe and remove it from the registry, reboot your machine, and the hijacking software will no longer steal your searches.
You can then remove the offending program or dll at leisure.
I had the same thing happen to me with "MyWay" and tried everything to no avail until I ran into "Hijackthis".