I experimented a bit more and found that $M=S/B$ measure is fairly robust even if some underlying assumptions are relaxed. Of course, you can beat it if one set is more eager not to make its disorder observable than the other one, which will result in both a lower $M$ and a lower observation rate, but how do you know it is really hiding something? In other words, why are you so sure that the sets with different missing rates should really exhibit the same amount of disorder on average?

Anyway, it is up to you now whether to continue this discussion or to stop here. At the very least, you have a measure that is not sensitive to losing part of the data, which for me means that it doesn't "depend on size" any more. If you decide to stop, good luck with figuring out what the issue really is and feel free to return to this discussion if you want an outside opinion on something else :-)

I am reasonably confident (as much as I can be without being able to test this) that the assumption "the appearance of an object in the observation is more or less independent of its displacement" holds. The selection problem I am worried about is that the decision whether to sort a set or not is a black box to me. My prior was that this decision (to sort a set or not) was independent of the objects in the set, but I am now less convinced that this is true.

I would consider the question answered, and am interested to see your explanation regarding the reasoning behind it that you alluded to.

Sure. I'll post the rationale behind this particular choice of $M$ in the main thread when I have time. Meanwhile, it seems like your observations are more complicated than just observing partial samples of random orderings with different levels of noise, i.e., there is some sorting process in between, etc. However, it is mysterious why that decision or whatever other intermediate steps that occur before the sample is observed should correlate with the sample size.

Once you figure that out, you may have your puzzle solved. You may want to test what else correlates with the sample size that normally should not. If there are several such things, then we'll have to accept that the small size observations come from really different sets and there is no a priori reason to assume that the balancing test should be passed before some compensation for that difference is introduced.

So my general advice at this point (if you want it) would be to search for all correlations with the sample size that shouldn't normally be expected and see how strong they are. You already have one: between $M$ and the size. If you can figure out how strong it is quantitatively, you can just compensate for it by brute force but that requires rather strong faith in the validity of the balance you are checking, which may come only from the physical meaning of all those things.

OK, the derivation is posted. See if it makes sense for you.