Headers could maybe work in a world where the technology were ubiquitous and people knew how to set it up (c.f. v-chip's failures), and kids couldn't just buy their own device for $20 and use it on the actually ubiquitous free pubic wi-fi to avoid any restrictions.

And actually I think it's a better world where kids can obtain e.g. a raspberry pi that they completely control no questions asked and free public wi-fi exists all over, and the onus is on service providers to not deal with children if they're not supposed to. Basically, a high trust society.

In any case, "don't retain records" is actually a pretty easy task. Trivial, actually (use a device with no disk to handle PII, an API that just returns yes/no to the rest of the system, and heavily restrict the firewall, e.g. no outbound connections). Or you buy a token/gift card in person with ID check. If you think the penalties aren't steep enough to get compliance, just raise them (e.g. business ending fines plus jail time).