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.