You can put all of the state into the browser:
1. Site generates an AES key for the verification request. Gives it to the browser along with (short) expiration time in an encrypted cookie (so the browser can't see or forge the key). Encrypts a request to .gov (using .gov public key) saying "use <key> to encrypt a token for <requesting IP>". Gives that request to the user to present to .gov.
2. Browser asks user if they'd like to request age verification. Proceed.
3. Gov does ID verification. Checks requesting IP matches. Creates tokens for "over16", "over18", "over21", and any other magic ages that laws exist for, each individually encrypted with site AES key and IP-bound. Gives all tokens back to the browser so .gov doesn't know which will be used. e.g.
{
"over13": "<encrypted token>",
"over16": "<encrypted token>",
"over18": "<encrypted token>",
"over21": "<encrypted token>"
}
4. Browser asks user which token they want to give to the site (that could actually be part of step 2, and the site could indicate which one it would like).
5. Site gets single relevant token back, decrypts the cookie, and uses the key to decrypt the token. Checks requesting IP in response token matches. Checks token signature against .gov public key.
.gov only learns that some age-restricted service was requested, but not even which age. Server only learns user is over the required age. Browser can't see or modify any of the messages between .gov and site because they're all encrypted.
With such a protocol, adding more age-restricted use-cases (e.g. buying cigarettes/alcohol, gambling, social media/advertising/anything where you need COPPA's "I am over 13" assertion) would increase overall privacy.