To change the search engine for IE4, you will need to edit the value in the registry. Back up first and then open the following key:

HKLM\SOFTWARE\Microsoft\Internet Explorer\Main

Find the Search Bar string in the right pain. Double click on it and change its Value Data to match the search page of your choice.