Except that the implementation described in the post does use multiple GC cycles to settle if I read it correctly. It will only be an issue if you have reference cycles through ephemeron edges, though, like a key associated with a value that is itself or refers to an otherwise-dead WeakMap which contains a key associated with... etc.
Multiple cycles are not fundamental to ephemeron collection, though. If you keep all of your unmarked keys (specifically, keys of ephemeron tables that have been marked) in a lookup table, then in theory every time you mark anything you could look it up in that table to see if you need to traverse an ephemeron edge. In practice, you probably don't want to do those lookups until you've traversed the "easy" part of the heap that doesn't require traversing ephemerons to get to.
Multiple cycles are not fundamental to ephemeron collection, though. If you keep all of your unmarked keys (specifically, keys of ephemeron tables that have been marked) in a lookup table, then in theory every time you mark anything you could look it up in that table to see if you need to traverse an ephemeron edge. In practice, you probably don't want to do those lookups until you've traversed the "easy" part of the heap that doesn't require traversing ephemerons to get to.
Source: that's how I implemented it in SpiderMonkey: https://searchfox.org/mozilla-central/rev/552bfc6334b797d92f...