So it turns out my initial intuition about going through the children was correct. Something similar to this where you iterate on the child elements, while perhaps not performant in some cases, offers much better guarantees about redacting all related info.

        // redact any descendant Rects that are not fully contained within the parent
        Queue<Element> redactedChildrenQueue = Queue.from([currentElement]);
        while (redactedChildrenQueue.isNotEmpty) {
          final redactedChild = redactedChildrenQueue.removeFirst();
          final childRect = _getGlobalElementRect(redactedChild);

          if (!childRect.isEmpty && childRect.intersect(elementRect) != childRect) {
            redactionRects.add(childRect);
          }
          redactedChild.visitChildElements((child) {
            redactedChildrenQueue.add(child);
          });
        }

Result where label is redacted: