Error "Internet Explorer could not install this search provider" when adding a Search provider

Symptom

When you attempt to add a Search Provider, the following error message may appear:

Internet Explorer could not install this search provider.

There was a problem with the search provider's information.

Resolution

Click Start, Run and type:

regsvr32 %SystemRoot%\system32\msxml3.dll

Press Enter.