I would guess it depends on the amount of reuse. Mario 64 (although I believe Super Mario World did it first) had a fair amount of level 'reuse' in that there were multiple goals to the level. Instead of creating five different levels, they used one level and placed a good deal of content within that level. This forced players to interact with the level multiple times, sometimes solving a puzzle in different ways while not forcing the player to replay the levels simply for the sake of replaying the levels.

On a certain level, I wouldn't say that Diablo really reused levels. The rooms themselves were the same, but since they were put together differently you had different levels. For me, the only way in which they were really reused was the fact that you dealt with the same tileset for four levels in a row before you got a change. If, for example, they made their random level generation quite a bit more robust (example, instead of having whole rooms pre-made, they would randomize the room construction and then build the level with the rooms, or if you actual built a dungeon which made sense instead of just a bunch of random rooms) and added in variance to the tilesets (say at certain parts of the dungeon the wall would break down into tunnels) then it would detract from the feel that you were in the same area.

Since I personally think there is a difference between level reuse and randomized levels I'll answer the question about level reuse, specifically, what does the level require. Simply put, the level has to be extremely well designed. If a person only plays through a level once, you can try to assume that they won't notice most flaws or that they'll be more forgiving if only one area is a little frustrating. However, if you have the player repeat the area, you're going to want to doubly make sure they can't get stuck in inane places, that there aren't any cheap, unavoidable traps or anything else that only serves to aggravate the player. Of course, you're going to have to have a good reason why the player would want to replay the level in the first place. To me, I think the answer would simply be multiple goals for the player to achieve (like Mario as I touched on before).

But this is all thinking on a strict level idea (ie, the player progresses through a series of levels over and over). Most RPGs have 'level' reuse (by level I mean map here) where the player might repeatedly revisit a town or a city through various parts of the game. I guess this just leads back into providing that there is a reason why the player would return to the level.

Anyway, that's just my view on the whole thing.

One of the most common complaints about Samurai Western was that there were only about six actual areas, and you just kept going from one to the next fighting different enemies at different times of the day. I rather liked that, because it made the game seem more "local". Rather than the "clear and advance" sort of design, it provided a familiarity that tied in well with the game's story (such that it was). You had the boom town, the ghost town, the mine, the wilderness, the old fort and the villain's estate. Travelling around the area and meeting the same characters in different scenarios was refreshing for me.

Besides, the levels were usually presented with different paths and enemies, and you hardly noticed with the mindless slicing and dodging that occupied your time throughout gameplay.

I would certainly be willing to accept such a format in another game.

Another note: Games like Escape Velocity use a finite number of settings, but the player seldom becomes bored with them because they aren't simple obstacle courses. They're actual locations, and you can inhabit them to such a degree that travelling among them is less uninspired adventure than it is a commute or assignment. When you hear that bandits are attacking Aunt Rose's place, you head over there without thinking, "Aw, man! I've been down this same street like six times already!"

I guess the difference is whether the gameplay depends on novel travel experiences, or on work you get done at the destination.

My brain isn't really working well, so I don't have much insight or comment.

But I think I'd bring up Trade Wars. Again you have a proceedural Level (world) Generation.

There is alot of emphasis on Exploration and Collecting Locations for resources (finding port pairs and bubbles).

The arrangement of the Randomly generated world is a HUGE part of the game. And ultimately it is nothing but a graph of connected rooms with resources randomly distributed.

Just thought I'd bring it up as something to look at.

One thing a lot of games do wrong is doing the exact same thing a bunch of times. Sometimes a 'twist' is all that is needed to make it new and interesting, but a lot of times, the twist isn't good enough, and players get REALLY bored with the level. The Grand Theft Auto series is a great example - they have a few unique missions, but a majority of the tasks are very repetative. In my opinion, the games don't offer enough twist for the repetative nature of the game.

On the other hand, some games are BUILT on repetativeness. Look at any racing game or golf game - take Gran Turismo; the entirety of the game is spent racing a car. There's like three different types of races and a few tracks, so each race is fairly similar to the last. They offer over 700 cars, but so many are similar, your racing experience is limited to much less variety. The fact is, the game being repetative is what makes it so much fun to play. The same is true of Gauntlet II, but to a lesser degree.

I think the idea is to make sure you have the right amount of 'twist' for your repetative experience. The simpler the game, the more repetative it can be. Halo 2 should probably have less level reuse than Super Mario Bros, and not just because it's a newer game, but also because SMB is a simpler game.