If I were drafting the regulations (fortunately I have neither the legal nor technical expertise), I'd make it legal to store without permission a cookie containing only a specific string defined by the regulation, e.g. “optout” or “0”, meaning “this user has seen the question and opted out; don't bother them again”. The regulations would have to ensure that the cookie's timestamps are suitably generic to prevent fingerprinting — perhaps you can store a date but not a time.

Would something like that work?

(Edit: Ah, apparently this sort of thing is already allowed, according to comments I didn't read before writing this. Sensible legislators.)