The explainer talks about having a low entropy identifier for each browser. This appears to be so that Join requests from the same browser can be linked. That is, a browser can refresh Join they previously made without contributing toward the threshold.

This might also reduce the total state exposure of the k-anonymity server. If $j$ bits of data are used, the server only needs to keep $2^j$ items for each hash. That's still an awful lot, but there is now a cap.

Concentrating on the first one, I think that this is better addressed by having the client simply indicate when it is refreshes an existing item. The client could provide an approximate (noised) estimate of when the last entry was added or how long since the item was last added. My sense is that you could tolerate a lot of noise on this estimate and still have a functioning system that doesn't have a persistent identifier client involved, even a low entropy one. The time granularity only needs to be the period ($p$).

The state limiting thing is not really that big of a deal. A server can maintain a count for each period in the tracked window ($w$). Then the server only has to maintain $\frac{w}{p}=720$ numbers for each, which is plumb between $j=9$ and $j=10$ if you are just counting state¹. Refreshes just mean moving one count from a previous period to the latest, as opposed to just adding to the latest.

There is some clever rate-limiting token stuff that can be used to prevent a client from refreshing too often, if you really want to go there. You could also issue unlinkable cookies that are bound to a specific period. I don't think that you want to do any of that, but I'm mentioning it just in case.