The answer seems to be:

I took the gamble and saved their uninstaller at http://lop.com/new_uninstall.exe - I ran it and the prosearching toolbar is gone - the problem seems solved.