After an operation that manipulates the DOM (node insertion or removal), we traverse the affected subtree twice: Once for setTreeScope/DocumentRecursively, and once for insertedInto/removedFromDocument/Tree(). We should be able to combine the updates into a single traversal. Note that this applies to DOM manipulation outside of shadow DOM as well, but shadow DOM exacerbates the problem.
This will be too complicated because the insertedInto/removedFromDocument/Tree callbacks will need to deal with TreeScope state that is not globally consistent.