Malicious compliance. You do not need a cookie to "store" the fact you have rejected them. They can simply assume you have rejected them from the lack of cookies. They can store a cookie once you (have gone out of your way to) accept them.
Lack of cookies could mean you never visited the site before.
Lack of cookies could mean you never visited the site before.