I doubt this doesn’t actually leave a paper trail.

At some point, you send that nonce to an age-verifier service. So they can keep track of it, and if the 18+ website you visited at some point later wants to know your identity, they can ask the age-verifier service who asked for that nonce to be signed.

This involves that two organizations are corrupt, however: both the 18+ website and the age-verifying service. Law could mandate that they both cooperate, however, thus creating a single point of (privacy) failure.

I still believe it is doable, however. Check my other comment involving a piece of paper that is drawn from a box. My method relies on the fact that the age-verifying service doesn’t actually know which code they gave you, just that they gave you one. For digital services, seevices can always keep track of their input/output, which is not always possible in real life.