I'm not a developer, but I suspect something like this is going on:
If browser.sessionstore.enabled is set as TRUE(which it is by default), the session store feature kicks in when you exit Firefox and takes a backup of all the cookies from the default location where they are stored. (I think in %appdata%\Mozilla\Firefox\Profiles\xxxxxxxx.default\cookies.sqlite)
When you run CCleaner, it cleans the cookies from the default location and reports that the cookies have been removed.
The next time that you start Firefox, session restore restores the cookies from its backup, back to the default location.
Et Voil?! Your cookies are back from the dead.
If CCleaner needs to stay effective, it might have to find a way to get at session restore's backup data and remove it from there as well. Mind you, I don't really know if this is exactly how it transpires. I'm only guessing.