Actually, what you are saying is simply that one
algorithm is better than the other. For one particular problem. You can search all word combinations, or search all dictionary words. In this case, searching all dictionary words is more efficient.
However, if you are dealing with computer programs, to improve on the naive method requires the code to be extremely simplified. We already have an
example of this. By the authors' account it consists of around 800 instructions and there is only a main loop without hardware interrupts. That's what makes it possible to simplify everything and perform the search.
With respect to the game this was discussed (SMB), one possible situation that a movement simulation does not cover is some sort of ACE setup that could glitch Mario through all the stages at enormous speed. Ruling out ACE quickly becomes unfeasible as the code grows in complexity. Moreover, for the particular submission, a shorter movie was presented. That alone suffices to prove the simulation in question was not complete.
It's like, when someone says "to make a computer play chess, you have to search millions of positions", and you reply "not really! chess might be one of these games where you can find a winning strategy without
searching. While that really is true, there's no reason to believe we are anyway close to finding such strategy.
Extraordinary claims require extraordinary evidence. At some point if some guy comes up with a formula that plays chess perfectly, you have to ask what is more probable. That chess players and AI researchers for the last centuries all missed a key point in the game that someone eventually discovered like pulling a rabbit out of a hat, or that his/her proposed solution contains a mistake. In general, when something seems too good to be true, it usually is.