How can you store that information in a compliant way?
My initial thought is to use a cookie, but would that be non-compliant? They did just refuse the storage of cookies on their device... And if I store it in a database somewhere, how am I supposed to associate that refusal with that user if I can't store personal information?
According to the accepted answer to this question, you can use a userId or some such. But first of all that is in the context of consenting, not refusing, to cookies; secondly, if that identifier is associated with a user, then by definition it is personal data (right?) and therefore storing that information would be non-compliant.
Regarding the storage of consent, is it enough to store that in a cookie on the user's device or do you really need to store it in a database somewhere? That really seems superfluous to me.