I’m intrugued by that because AFAIK the cookies are not listed in settings. (you have to go into the Developer tools to see the cookies in Firefox, and it’s not simple).
However that’s by the by.
Do you have “Restore previous Session” set in Firefox?
Firefox pre-loads cookies when “Restore previous session” is enabled in settings, specifically accessing cookies from the last opened sites to ensure a smooth page restoration.
So if you have that set then even if you have cleared the cookies Firefox will go and get them again next time you open it.
The bit about CCleaner showing them again if run again straight away is interesting if it isn’t saying ‘Skipped’.
You say that you are using CCleaner Portable - is that the official Portable from the builds page?
Download CCleaner builds | CCleaner Portable, Slim, and more
Or is it a repack from a 3rd party website?
Are you runing it from a USB stick, or is it saved on your computer?
Again; if you would post a screenshot showing your CCleaner settings for Firefox, and the cleaning results (similar to my first one above) then it may help us work out what is happening