This may be expected behavior.  Cookies per top-level-domain are capped, so if a single domain sets a ton of cookies on a variety of its subdomains, it will eventually run into the per-domain cookie quota.  We do have some heuristics to try and figure out which cookies to keep longer (Favoring secure cookies, and higher priority cookies), but it doesn't look like live journal uses either cookie priorities or secure cookies.

Thanks a lot for diagnosis! Explains lots.
So am I correct that you mean additional flags `Secure;Priority=High` on more important cookies? 

Correct, though if you set too many cookies, you'll still run into the issue.  We keep 150 cookies per top-level domain.  When purging cookies, we keep 30 low priority cookies, and 50 medium priority or lower cookies (i.e., we will delete higher priority cookies, to save that many lower priority cookies, if the lower priority cookies were set more recently).  We'll actually wait until 180 cookies are set before destroying cookies, but then we'll delete 30 at once.  If there are no secure cookies, we'll keep 150 medium cookies, etc.

You don't need both Secure and Priority=High - one or the other should do the trick.  Secure cookies can't be read, deleted, or overwritten by HTTP (non-HTTPS) requests or pages, so they may or may not work for your use case.

The actual algorithm is:

Figure out how many cookies we need to delete (num cookies for that domain - 150).

* Try to delete that many low priority non-secure cookies, oldest first, keeping at least 30 cookies of those types.
* If not enough cookies were deleted, try to delete that many low priority secure or non-secure cookies, oldest first, keeping at least 30 cookies of those types.
* If not enough cookies were deleted, try to delete that many medium priority non-secure or lower priority (secure or non-secure) cookies, keeping at least 50 of those types.
etc.

There are also rules for expiring cookies globally, which are based on total number of cookies, but those are deleted in order of age, and we don't delete cookies set less than 30 days ago when doing this, regardless of total number of set cookies, so that's unlikely to be the issue here.

Thanks for such a detailed view! I think there will be demand for that info.

Team is already in the process of testing the flags on selected cookies. `Secure` gives a few issues, yes, so currently it's just a `Priority=High`. Even while alone, this flag seems to work and helps selected cookies to persist.

I'm going to go ahead and close this bug, but feel free to ask questions here, or via email, if you have them (Or it turns out there is a bug here, I can reopen the bug).

Agreed, no bug here! Let's close it.