Please note: this tip is for Outlook 2003 and older. It does not work in modern versions of Outlook as the Web Toolbar was removed.
When you use Outlook's Web toolbar web search button to conduct an Internet search from within Outlook's window, Outlook uses the search engines configured in Windows and installing search engine toolbars can change which engine Outlook uses.
Windows holds the search engine urls in registry keys. Some of these can be changed within IE, by opening the Search bar and choose Customize. Check the settings under Search Assistant, Use one search options and Autosearch settings button.
Outlook's Web toolbar seems to use the Search Bar registry key and none of the search settings seem to control it, so you'll need to edit the registry to change it.
Open the registry editor and browse to
[HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Main]
Find the Search Bar value and change the url to your desired search engine.
Published September 29, 2005. Last updated on September 23, 2013.