Every time I open Internet Explorer 10 on a Windows 8 laptop, it pops up with a message "A program on your computer has corrupted your default search provider setting for Internet Explorer. Internet Explorer has reset this setting to your original search provider, Bing (www.bing.com). Internet Explorer will now open Search Settings, where you can change this setting or install more search providers."
Things I have tried so far:
Resetting IE10 defaults (In Internet Options>Advanced>Reset...)
Checking the User Shell Folders AppData registry key
And the fix that commonly fixes the problem, deleting the CREDHIST file in the %appdata%\Microsoft\Protect folder
And it's still popping up. Any suggestions?