Eu concordo com a sugestão de @llion de definir uma expiração nos cookies, nesse caso você pode agenda um processo para limpar os cookies expirados do dB. No entanto, você pode fazer isso parecer para o usuário quase como se os cookies fossem persistentes indefinidamente por prolongar a vida sempre que você os vê.

Para o benefício de qualquer outro leitor interessado nesta questão, espero que você esteja apenas armazenando hashes do cookie em seu dB.