I have updated #26711 with a new approach (linearization to help group txns, then submit ancestor subpackages, abort all if there are non-fee failures). No more O(n^2) validation. Though there's a CI failure I need to fix.
I've been spending time thinking about next steps, which is the integration into net code, where I'm beginning to feel some restructuring of the code would be better too.
In particular, currently all the packet checksumming happens inside the net_processing thread, while the packet checksum verification happens in the net thread. It'd be both cleaner, and I think more desirable from a resource allocation perspective, to do both in the net thread (which is generally low computationally).
So I'm looking into seeing how big of a change that'd be, and if it's not too much, that's probably the next PR I'll open.