IE8 RC pops a message about bad search provider

I got the following annoying message after installing IE8 RC1

Internet Explorer - Search Provider Default
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, Live Search (search.live.com).

Internet Explorer will now open Search Settings, where you can change this setting or install more search providers.

 

I tried everything (change default, remove all providers) and nothing worked so finally I found the non trivial solution:

1. Delete registry - HKCU\Software\Microsoft\Internet Explorer\User Preferences
2. If it didn't resolve the issue then also remove the Google entry from registry from HKCU\Software\Microsoft\Internet Explorer\SearchScopes (make sure it's not default)

This will save you some headache