But if you were trying random solutions and the solution tester was a black box

Then you're not solving the same optimization problem anymore. If the black box just had two outputs, "good" and "bad", then, yes, a black box that accepts fewer input sequences is going to be one that is harder to make accept. On the other hand, if the black box had some sort of metric on a scale from "bad" going up to "good", and the optimizer could update on the output each time, the sequence problem is still going to be much easier than the MP3 problem.