Listen, you are correct. Having more prefixes found, in N attempts, after you found a bunch is less likely. So you are entitled to say there will be less found, in N attempts.

I have an upgrade for your theory, please tell me where I have it wrong.

Instead of looking at the range and thinking "hey, less chances of it being here", let's replace that range with some set (just replace the keys of the range with some other keys).

Now, you have less chances of finding more keys in the remaining keys in the set.

So what happens? Well, since you dismiss the rest of the set, you end up going with the continuation of the range, as the "best" new keys that have better chances of finding the prefix.

Do you see the problem now? It's a zero sum game. But my upgrade makes things a lot faster. All good now? It works in perfect accordance with your theory.