It’s strange that the region would have any impact. When I moved from the US to Canada, I changed my region and was still able to get updates. The one thing that the region would affect would be the Microsoft Store.
From how things are described I almost wonder if it was a VPN issue? Still, on or off VPN you should still be able to get updates; and the fact this was happening on multiple machines is what makes it even more unusual.
Edit: Fired up an old laptop and changed regions, checked for updates, and they were found, no issues.
I really want to know what the issue was. Assuming it may have been cause of the VPN but unsure. Either way, glad you got it resolved.