I am not familar with AsSequential (I don't think I used it in my standalone prototypes), but we should make sure its implementation doesn't use the same MergeSortCooperatively that was causing the problem.

I wasn't either! My impression from the docs was that it was basically just "give me an IEnumerable out of this parallel thing" so it's WhenAll, and shouldn't have any blocking. But if it's not necessary I'd also prefer to remove it.

AsSequential unwraps the underlying IEnumerable (effectively undoing AsParallel) to make sure that the OrderBy doesn't use the problematic parallel implementation. As such it cannot be removed if we want to keep the whole thing in one query.

The prototype had a list of tuples as its final product, i.e. it's missing the sorting which is required to make List<ProvenanceResult>.

First of all, thanks @adrianvmsft for detailed analysis you did for this issue. As my colleagues noted, AsSequential switches from PLINQ (ParallelQuery) to standard enumerable. I wanted to avoid sorting in parallel way. The question is, if the sorted collection has some benefit. Tests are passing after removing OrderBy, but maybe there are some perf implications in further processing of this collection.

Thank you!
I tried a similar query (using AsSequential) in a standalone app, and I can confirm that it does not hit the MergeSortCooperatively function.