Remove its entry from the registry - this will most easily be done through Hijackthis. select its entry and have it fix it... Delete the source file also.
If you cannot delete the source file, try timing the end task, then immediately deleting - it sounds silly but I have done this before... Sometimes it is the quickest way to get rid of something nasty like this:
Open up the folder containing the file that will not delete. Open task manager. Follow this in immediate succesion - end task on target process, right click on file, press "d", then "y" on the keyboard.
If you are quick enough (VERY quick), you can delete the file before it has an oppurtunity to be re-engaged by the process restarting.
Or you could just go into safemode and delete it, as it probably doesn't run in safe mode. You should go into add/remove programs and make sure there is no junk like search tools or suspicious garbage listed there.
When he runs spyware tools, what infection is found every time? It is trying to fix this, but just can't because its running... If you let me know what its finding, we can probably give more accurate instructions.