The first solution would be to generate the levels dynamically. I'm fairly surprised nobody yet came up with algorithm that would generate weird playable levels for example for Quake 3, Half-Life 2 or whatever FPS is currently fashionable (at least i don't know about it). Using this approach, you could have whole planets that you could run through in 3D! Of course the problem is creating the algorithm but I'm surprised no one even tried in the current-generation games (except some basic puzzle games).
The second solution is to make the game worlds so simple levels can be generated very quickly, either by person or by rather simple algorithm. Remember Sentinel with 9999 levels? See also Angband with its dynamically-generated RPG levels ("Champions of Norrath" for PS2 recently attempted something similar, with average success).
Enter Nippon Ichi, Japanese authors of turn-based RPG games for Playstation 2.
As you can see from the screenshot of their "Phantom Brave", they are certainly brave to use such a shitty graphics in Playstation 2 game. However, their games are not about graphics. They are strategy combat games for hardcore gamers who enjoy leveling their characters up to level 9999. Yes, I wrote "9999". After 10 hours of "Phantom Brave", my main character is somewhere around level 15.
To create strong characters in their "Phantom Brave" and "Disgaea" games (and probably also in the others), player has to revisit old (pre-designed) levels he already conquered, preferably with secondary characters so that they can also level up accordingly.
Their games also contain billions and billions of randomly generated levels you can enter to level up and get rare equipment (even levels hidden inside your equipment). It doesn't hurt that their games have weird plot and bizarre sense of humor ("Disgaea" is about cute little Satan's son), but you really don't play them because of the plot.
This might seem pointless to some people but it brings us back to the beginning: Why do we play games? Try telling "World of Warcraft" player that his levelling up is pointless. Nippon Ichi games just help you to realize that - even today - it can be perfectly satisfying experience just to see some numbers increase on the screen.
"Phantom Brave" is currently available in European stores, "Disgaea" (older and slightly better) is hard to get but you could find it in some bargain bin somewhere. (Their "Makai Kingdom" should be released in Europe soon.) Visit DoubleJump forums to get free downloads of strategy guides for both games. Those are REQUIRED if you want to grasp basic concepts.