This isn't really my area of expertise, is there a way to know for sure that those are all the same token? Or could the government just lie and say they are all the same when in reality they can really differentiate.
The government would have to document the API for requesting tokens for anyone to use it. I suggested a scheme here[0] where it's clear that the government doesn't get any information about the service (unless the service re-uses AES keys) and the service doesn't get any information about the user other than whether they're in the appropriate age group.
Potentially there could be coordination between .gov and the service to track users by having each side store the temporary AES key and reconcile out-of-band. But .gov has other ways they could get that information anyway if they have cooperation from businesses (e.g. asking your ISP for your IP address, and asking the service provider for a list of user IPs).
