A new hotfix (KB2171141) is out from Microsoft that resolves an issues with the IE8 search provider when applying the “Prevent Internet Explore Search box from displaying” is enabled (see image below).
This policy will remove remove the search box from Internet Explorer (see image below).
But then when a user logs on to the computer for the first time they are prompted to setup their default IE setting and then they will get this error message (see image below).
It also looks like this hotfix is also probably not going to be in Windows 7 Service Pack 1 as it is not listed in the complete list of hotfixes.
To download the hotfix and to get more info visit Internet Explorer 8 restores the search provider settings when the “Prevent Internet Explorer Search box from displaying” Group Policy setting is enabled