Good news! I have a fix!!!
After further investigation I discovered that the web service that is failing is not actually responsible for the search itself. All it does is provide Media Center with a bit of meta information (the "search taxonomy") about what its Internet TV search
providers are, and what sort of filters they support. Most of those were for the old Internet TV channels that are all gone anyway. All that really remains is Netflix.
It turns out you can override the search taxonomy URL with a registry entry. So I created a simple Windows Service that acts as a local substitute for Microsoft's broken server, and serves up a dirt-simple SearchTaxonomy document with the minimum necessary
information to allow Windows Media Center to initialize the Netflix search.
You can download it here. Extract the files to a local directory (not on a network drive!), and run Install.bat with the "Run As Administrator" command.
Once installed, the netflix search should just work.
The code is hosted on GitHub, if you're curious about the technical details.
Enjoy!
Binaries: https://github.com/revengineering/MceNflx/releases/download/v1.0-beta/MceNflx.zip
Source: https://github.com/revengineering/MceNflx