Make some of the locks unnecessary. The only game to do this that I'm aware of is Metroid Fusion.
...widely regarded as the weakest in the 2D series.
I agree with most of that post, but not the last bit. Using your shiny new key to get to where you've already been is frustrating. Super Metroid (widely regarded as the strongest) did pretty much the opposite; every time you got a key, you already knew of several places you could use it, and every one lead you to someplace that was new, or either important or useful.
Example of what Super Metroid did right, via example of what Super Metroid did wrong: That glass tube. The goddam glass tube that you have to Super Bomb to proceed farther into the game. It shows no signs of taking damage from any other weapon, so there's no indication that it's anything other than a particularly pretty room - and since Super Bomb is one of the last weapons you acquire, even if you
did attack the tube with other weapons, by the time you get Super Bomb you're probably convinced that the tube can't be broken (I mean if Super
Missiles didn't work...).
But the
real reason that glass tube was a problem (okay, probably just for me, but bear with me) is because it's the only time in the game that happens. It's really the only time in the entire game that it's not
very very clear that "you can use x item right here". Sometimes it's flat out marked with a symbol, and other times it's obvious (space jump, open ceiling), but other than
that fucking glass tube there's no guesswork about it at all. That's why Super Metroid is an "exploration" game and not a "puzzle" game, and why most people think it's "fun" instead of "frustrating".
(Here is where I resist the urge to dredge up SotN as a negative example. Fuck you, you know it is.)