Hiya
You may want to try this for uninstalling IE6.
Go to the Control Panel | AddRemove. Put a tick in "restore to previous windows configuration", then a tick in Add A component, instead of Repair. Follow the prompts and select Internet Explorer. Ignore the warning and reinstall it anyway.
With the Search part, are you getting any search engines to work? What I mean is, if you click the button, you say you get Page Cannot be Found. Your Search Engine name may be wrong.
You may also want to have a look at this:
http://forums.techguy.org/showthread.php?threadid=56650&pagenumber=1
Not really the same issue, but it talks about the Search facilty. One bit in particular, but we may need people more advanced in the registry to find it, is this:
The Automatic Search URL is configurable by using two parameters denoted by a percent (%) sign. These two values must be part of the URL itself. The value %1 represents what the user typed in the Address bar. The value %2 represents the type of search option chosen by the user. Possible values for %2 are 3, 2, 1, and 0, where:
3 = Display the results and go to the most likely site.
2 = Just go to the most likely site.
1 = Just display the results in the main window.
0 = Do not search from the Address bar.
Now, you may have 0 set somewhere. Mine must be set to 1. What this means is, if you have Do Not Search, it won't search.
But, if you try the uninstall back to IE5.5, and see if it works again, we may not have to try all that blurb above
Regards
eddie