Roguelikes proved this point decades ago, it's just that they have a persistent problem that turns most people off: playing such a game by its rules (random starting characteristics, no continuation upon death) without any attempts to modify them takes by far the biggest balls it can ever take in a videogame world. This is like an arcade game that is highly random, highly taxing on brainpower, and very long, all at the same time. Some games also cleverly implement things analogous to rank in arcade games, where the better you play the tougher the enemies become. It is truly an awesome genre of games that is so often and so undeservedly overlooked. Spelunky owes everything that makes it such a cool game to this genre.
Super Metroid was one of the first games (or maybe the first) that actually legitimized sequencebreaking. It would urge you to take a more-or-less fixed route at first, but as you beat the game and see the attract mode demos, it dawns upon you that there's a gajillion of undocumented abilities that change the game completely and make it possible to have at least 2-3 solutions to every obstacle on your way. This was why the game was so great and this was why Castlevania went that exact way with SotN (which, aside from extremely poor power balance, did everything perfectly in that respect).
I still play Super from time to time, and maintain a trick page about it on TASVideos.org, which is, even though incomplete, by far the most comprehensive list of advanced Super Metroid techniques on the web. Needless to say I came to dislike Fusion after I realized it's completely and utterly linear in pretty much every respect. It's a Zelda game, not a Metroid game. And Retro were a bunch of douches for artificially limiting Prime series' sequencebreaking. That was an utterly retarded thing to do, as if they didn't even understand what made Super and Prime as good and lasting as they had proven to be.
But there is another point to consider. Take Scribblenauts, the game that was initially heralded as the most impressive sandbox game released to date, with lots of lasting appeal, etc., which seemed far-fetched initially (because making such claims is a pretty stupid thing to do, as history has proven repeatedly). And what was the result? The game is a one-trick pony. As soon as the novelty wears off you realize there is no challenge whatsoever because there are always several obvious solutions that work 99% of the time. A good puzzle game would never make its solutions obvious past the first few levels, which is precisely why everything known as a good puzzle game has lasting appeal. The guys that screamed how great Scribblenauts was at release should've known such a simple thing.
Another classic example of excessive open-endedness ruining replayability is Portal. I mean, I know Valve has to cater to people who aren't that good with puzzles to expand their audience, but hardly anybody denies that the only challenge the game presented initially was technical (doing a sequence of movements in a short time frame), and not conceptual. The puzzles were, in fact, really really simple. If not for the great atmosphere, humor, and challenge levels (which were hardly a challenge to speak of, but still far better than the original versions), I wouldn't even like it at all. The game was only made fun by artificially making it more challenging, like limiting the amount of portals per map, or playing it for speed (and thus facilitating more efficient solutions). I'm now waiting for Portal 2 with a hope that it'll make things more interesting from the get-go.
What does that mean? I think that having several solutions to any given problem is a good thing. But human attention and love are still needed to make solving problems fun. Fun comes from challenge (as a reward) and the fact that you've come up with something that works (as an affirmation of your capability, which overly simple games rather tend to insult). Procedural design with lots of leeway thrown in will never by itself grant the game its replay value. Spelunky would have been a forgettable experience for me if not for the challenge and the fact that I've stopped playing it for survival as soon as I beat it the first time. Since then I only played it for speed, and achieved remarkable results. I purposefully played the game the only way it was fun for me from that point, which is the reason it never had a chance to become boring.
On the other hand, if a game is deep, challenging, and allows for applications of out-of-the-box thinking well, like ADoM or Nethack, it becomes a remarkable experience that makes learning it a neverending process, because you will always stumble upon a thing you haven't tried before. I wish more games (obviously aside from puzzles, since it's their job to begin with) were like that. Since Super Metroid, Fallout 2 has probably come the closest. Aside from that? Dunno, Worms? Out of indie games, Within the Deep Forest and Iji have done the best, I believe.
