I also had the same issue. I believe I would classify ICQ as a browser hijack in its current state. It does not ask if you want to install the toolbar, it does so whether you want it to or not, when you install the newer versions of ICQ.
I am unsure of what web browser you are using. With Firefox you cannot uninstall the toolbar from within the browser in the addon's section. It has an uninstall/disable button, however, if you truly want it gone you have to go to control panel - add/remove programs and uninstall it (the toolbar).
This solves one issue. The next is the fact that anytime you type anything in your browser address bar it is ran through icq search. I typed in a valid website address and instead of actually going there it went to a search page with the site listed (as the same url i typed no less).
To solve this issue in firefox you have to type in your address bar type about:config.
It will bring up a screen giving you a warning that if you change anything you may "void your warranty." Click the button and it will bring you to a page with internal browser settings. Be extremely careful only to modify the one you are looking for dealing with icq search.
In the "Filter" box, enter "keyword.url"
-- Notice that the value is an ICQ search URL
-- Double click the line and an edit box will pop up
-- Copy and paste the following line as the new value
Google
Hope this helps.