I got caught as well - managed to delete most of the crap and all the toolbars except on my default MS IE home page will not stay at www.google.com.au but returns to:
Firewalls are not the problem. On our setup we have three plus three anti virus programs, two servers, one Linux box dedicated to all things email and internet. Incidently we would log 100’s of virus infected emails a day and we are only a small company.
Actually I tried what you suggested changing the home page through tools, options. Did the trick for a while but it came back. Looks as if Ad Aware and SpyBot finally erased the offending passthrough when I booted up my PC in safe mode.
I got hooked when I inadvertently opened a spam email instead of deleting it.
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.