To scan entire range (to get 100% probability of success), your method requires same number of ops as bruteforce (so it does not break any math laws), but it has better changes to find the key faster than bruteforce because it has non-linear probability of success (higher at the beginning and lower at the end comparing to bruteforce). Nice!
So if I have N uniformly distributed colored balls in an urn, and it takes a
hash(ball color) op to label every ball after every extraction, in order to compare the label with the target (or even to check the prefix), you are saying that the prefix method will extract the winning ball sooner, because you're stashing separately groups of balls.
If the prefix check would be a free or cheap operation, I would agree. However, the balls have no markings or clues on them in regard to their eventual label, and the average costs of both methods are the same, so the fact that the prefix method loses more badly (more operations) in the cases when sequential wins, is not accounted at all. Otherwise, the averages would not be identical. There's also no "loser" here since both methods account for the actual total number of ops to solve each hidden value.
For each his own though.