My issue ended up being because of network isolation/boundaries for store apps, because of a default firewall rule triggered by forced tunneling on our SSTP VPN.
Issue and resolution is described in this Microsoft document:
https://learn.microsoft.com/en-us/troubleshoot/windows-client/shell-experience/microsoft-store-not-open-domain-joine-computer-vpn