I think the "auto-search" provider should be the same as the default search provider. Use Tools/Manage Add-ons/Search Providers and make sure the word "default" shows up in the same line as the provider you want. You can also check off "prevent websites from suggesting changes..." at the bottom. If all seems ok, perhaps a restart of IE or a reboot will fix the "auto-search" provider. If not, you could also go to the Advanced tab of Internet Options to uncheck "Enable websites to use the search pane".
By any chance, have you ever installed the Bing Bar? If so, we may have to work on the Bing Bar uninstallation but hopefully that is not your issue.