Yes, I too wonder where those old cookies were stored. If CCleaner doesn't have 'logs', there has got to be someplace on the computer where these things were 'hidden'.
This should be addressed further by someone. These old cookies don't just magically reappear out of thin air. That's the purpose of running CCleaner!
Looking at the cookies section in the latest version (2.20.920), it says "This includes cookies from all internet browsers and Flash plugins).
I assume that all these old cookies that "re-appeared" were Adobe Flash cookies, and CCleaner only started cleaning these cookies when we noticed this problem. In other words, they have always been there, but CCleaner didn't know about them until recently.