It's not unbelievable at all, and it is well-known. It's been publicized that Microsoft sends every URL you visit in Edge back to Microsoft servers, tied with all the IDs on the device:
Are you talking about this post [1]? I don't see anything in the complaint alluding to a VPN license (for all we know he could have used an open source OpenVPN or Wireguard client to connect to the VPN), and the police seem to have gotten everything directly from Microsoft rather than from the VPN provider.
While this is Google and not Microsoft it's worth noting that Chrome literally has a telemetry option which sends URLs to Google [2].
https://www.itpro.com/security/privacy/355029/microsoft-edge...