I fixed my Windows Store issue thanks to
@military giving me a hint.
Windows Store now requires that IPv6 is enabled. No ifs or buts. But I am running a local dns resolver (Deadwood DNS) on my computer that binds to 127.0.0.1. So I knew Windows Store was working on the VPN but why was that and I figured it out.
Easy solution: Change your Wi-Fi Network Profile from Private to Public. Now Windows Store connects immediately without a hiccup.
More complex solution:
Using ::ffff:127.0.0.1 in the IPv6 DNS configuration fixed it for now. I am lucky because the IPv4 DNS servers I have chosen reply with IPv and IPv6 results so I guess DeepWeb is finally using IPv6!

All addresses are getting resolved, pinging works, tracert works. But I am unable to use nslookup through powershell since the resolver refuses to respond. I think this is most likely due to some security setting of the DNS resolver itself and not Windows.
For now I'm using the easy solution.