Well, after more than a year, dozens rebuilt servers (where the issue came back sometimes), trying all possible bing/google solutions that exist... I found the one that solved it for all my servers! I sincerely hope it will work for you as well as I think I lost half of may hair...
It looks like the issue lies within language pack (I couldn't find out if there is a specific one but I've seen with 2 different versions). No dsim, no packages, no changing serials, activations, etc...
What I did was...
- Install additional language pack (e.g. if there was US-EN, I've added GB)
- Set the display language of the server to the newly installed language pack
- Restart the server, remove previous language pack (in my case US-EN) and restart again
- All of a sudden... updates are going through on dozens and dozens of servers...
I hope it helps for you, too!