Randomly generated levels only keep their "freshness" if you do pretend Boring Brown Maze #5435435452 is different from Boring Brown Maze #4548575316.
I have to enjoy a game a lot to replay it. There's games which try to make you replay it by blocking the highest difficulty levels until you beat the game once - those usually don't get a second playthrough, as I like to be able to choose to make my game as impossible as I want from the go and work my way down from there if I can't handle the heat.
Games like the Dynasty/Samurai/Orochi Warriors are to me the best example of what makes me replay a game: Lots of things to unlock, absolutely *none* of them based on virtual dice rolls, plenty of characters to play as... Whenever I do a completion check on a DW game and I see everything I could do is done, I reset the save so I can do it all again. And the Elder Scroll games too, I can explore the maps time and again, and even though it's the same thing, changing the way I approach some things can make the whole thing feel new.
Here's what makes me replay a game, though usually more than one is required:
1- Either customization or enough characters to make customization unneeded.
2- Scenery porn. That is, the background/map mustn't just be junk thrown together randomly, but must feel like there's a whole world out there which I want to explore. For example, sometimes I climb one of Skyrim's tall mountains just so I can stare at the landscape. And I know sunsets killed me more times than I care to count on Oblivion and Fallout 3.
3- Main/playable characters I can like. The usual "guy/girl who's out for revenge for their hometown/dead family member/pony" thing is overdone and boring. See how the Elder Scroll does it, you're basically thrown into a mess you have to figure out, instead of being pointed at some silver-haired hobo and told "there, that's your enemy, we'll show you a supposedly sad flashback later on to justify this."
4- Can be played single player. I'm not a team player, and I care little about PvP except in some FPS.
5- It has some sort of New Game+ or "aftergame" mode which you can actually enjoy. Again, Skyrim is a good example, I don't have to feel pressured to finish all sidequests before beating the final boss, or load a save before the boss just to get them done later on.