From reading the official criminal complaint [1] it looks like Microsoft literally logs all web requests along with the GDID and sends it over as "telemetry". It basically associates the URL, the client's IP, and the GDID together.
Or I suppose it's possible that it only sends the domain and not the full URL, but that's enough for the police to go to the hoster and demand logs containing the full URL for said IP.
Clearly a bunch of defensive Microsoft employees are hitting these threads. The official complaint directly cites Microsoft as the source of these logs. They refer to Microsoft as the source of the records for web requests, app usage, and so on.
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].
Or I suppose it's possible that it only sends the domain and not the full URL, but that's enough for the police to go to the hoster and demand logs containing the full URL for said IP.
1. https://www.justice.gov/usao-ndil/media/1450651/dl?inline