There was never a blanket prohibition against cookies, that was a misconception (pushed purposefully by some, I suspect). Cookies which are "strictly necessary" in order to provide the service don't need to be approved. A cookie to remember that you don't want unnecessary cookies seems to fall well under that exception.

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.)

They could use local storage? As local storage isn't sent to the server, the server will not know whether the user opted out. (User opt in will be a cookie still.)

Alternatively, the legal definition of tracking cookie can differ from the technical definition of cookie. It wouldn't be the first time...!

The "cookie law" applies to every information that allows identifying the user which is not strictly necessary for the purposes of the service.

Cookie to say "has clicked no"? okay.

Login cookie? okay.

Cookie to track the user? not okay.

Local storage to track the user? not okay.

Tracking the user based on magic? not okay.

"Cookie law" is an informal name, the Directive itself refers generally to "stor[ing] information on the equipment of a user".