Linked-list freeing need not all happen in one go. There can be a queue of free-but-not-zeroed, push RC=0 stuff there instead of recurring on referents, anyone doing memory allocation work can pop a few items off that queue and decrement the counts of their referents, etc.

That loses timeliness, adds problem of queue management.

A weird trick I stumbled across years ago is to not strictly pop from the head of the stack/queue -- instead choose randomly from the last N elements of push end of the stack. This seemed to blunt the sort of growth that you get from "visiting wrong". I never did figure out the theory of why this worked.