I am having the same issue. In fact, it also happened for me with Cookie 4 and it's why I upgraded to Cookie 5 (hoping the issues had been resolved). It's definitely has something to do with how iCloud syncs the browsing history. Honestly, it makes me regret upgrading to Cooke 5.0... Why spend the money on the upgrade to get the same functionality?
disable the TImer,
open the Advanced panel in Preferences
push the Button “Remove All Sandbox Permissions”
click the "Open Setup Window" button
skip through to the "Choose Browsers" tab
disable one browser (any browser)
reenable that browser
skip through to the end,
and re-open Cookie
Cache removal is a must to remove ever-cookies.
It is also is all or nothing in Cookie - there is no distinguishing between favorite and non-favourite sites during cache removal. This is usually not an issue as any data which needs to be retained for login details tends to be stored in http-cookies or Local Storage/Databases.
There is no harm in removing cache cookies, although i wouldn't recommend it whilst the browser is still running as it can cause issues on some sites.
and, I think you should be ok enabling cache removal immediately, as no reputable sites store anything of much use in the cache...
huh, wasn't aware that this is such a challange. As Cookie is able to distinguish that a certain cookie belongs to what I call "top level domain", I thought that would be a breeze. Something like "oh, there's a new cookie! → does the TLD have a check mark? → YES → then this is a favorite as well". ? Okay, but it isn't that easy, right?