I think it can be proven by induction. Though, it most probably won't give you "sense of the things", you'll have that proof :)

So far my thoughts are the following:

1. Since we remove the leftmost pair, we can lay down the whole deck at once and then perform sifting. This simplifies further thoughts a bit.

2. It might be more convenient to count amount of unsiftable final positions multiplied by number of original permutations converging to them. Unsiftable positions will be of the form ABBAABBAABB.. or AABBAABBAABB.. due to suits restriction.

I think that multiplier erradicates most of (2n)! in denominator, and since history effect is 2-cards wide, the answer will be 2-polynomial.