The question here is how they were able to tie the GDID to a whole bunch of different domain visits. This is not something that is usually sent with web requests, and is not something that a typical web server config would log or be able to correlate.

The most plausible explanation I’ve seen is that some telemetry service checked in over the VPN, allowing Microsoft to log GDID<->IP, and correlate the GDID with other check-ins, from his real IP. If the VPN provider maps one IP per customer/session this would create a quite high confidence link.

Or he did something exceptionally stupid like being signed into a Microsoft account with enabled web history syncing enabled. Which of course would allow them to tie history

Remember, no matter what the commercial VPN companies want you to believe, a VPN only encrypts content between two points and masks your IP. It does very little for privacy on its own as most tracking is done with cookies and other session tokens.