> buy a card with a UUID from anywhere that sells alcohol/tobacco that is valid for some period of time

Exactly, prepaid phone cards with point of sales activation (to eliminate large scale theft incentive) is nothing new. Once activated, the validity of the token can be like 6 months or one year, and at-most-once-per-domain schema can be managed by the issuing authority if they want.

Instead of a 100 phone minutes, 300 phone minutes card you just buy "I'm over 16", "I'm over 18" cards. It's simple UX.