So setting up a new machine, I tried adding the Google search provider plugin for IE11; I wanted to add Google as my default provider rather than Bing. However, the Add-On kept failing to install:

The search provider could not be installed.
This might have happened because:

• A required file could not be downloaded
• The website is unavailable
• You are not connected to the internet

You might want to try again later.

Great. The problem was repeatable, and continued after reboot, and reset of IE’s settings. In desperation, I tried change the country that I was in (in the top right)…

I changed from United States to Turkey and back – and when I tried to add the extension, it installed without problem.

Hardly conclusive, but an interesting result nonetheless. Let me know if it works for anyone else!