[Lazy_Perfectionist]

Take a look at the Exiles/Avernum series by spiderweb software. They manage to provide quite a lot of replay value without random items or maps. The game world can actually change if you take too long to get something done, for instance, so you can take things in different directons.

There are cases for both situations, and both types of players. But personally, I find games with random items less immersing and decrease the original play value (and hence the replay value) considerably. If they're partially random, like as in Sacred or Divine Divinity, I can live with it. But if they're near completely random, as in Diablo 2, they never manage to hook me.

On the other foot, there's the whole niche of Roguelike games, but I won't get into that right now. I don't have that much to say.