tried it on IE 5.16 (german) after patching the version number as mentioned by erlmac: didn't work.
I therefore started Resorcerer and made the patch myself:
do a search for the string "http://home.microsoft.com/access/autosearch.asp?p=%s" or parts of it in resources of type "STR#". I found it at number 1000, string 344.
Replace its contents by "http://www.google.com/search?q=%s", save it, done.

Of course you can also set the entry to a different search engine, e.g. google.de.

- Julian