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.