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!
Andy Burns' Blog 
Your sir are a genius!
I never came across this problem before yesterday, then had it on two newly installed machines – one with Windows 7 Home Premium, and one with Windows Server 2012 Standard R2. It took a TON of fiddling on the Windows 7 machine before it somehow worked. On Server 2012 R2 I tried at least a dozen other suggestions before this one did the trick. Thanks!!!
Thankyou so much!! I’ve been having this exact problem on my Surface Pro 3. I Googled it and found various registry edits etc but nothing worked. Stumbled across this and it worked first time! It must be an issue with their site at the moment or something?! Again, thanks mate really appreciate it!
Awesome! You are my hero! \o/
Thank you so much for sharing this. I had the same problem, and this solved it.