Doom has been turned into a great RL, albeit a top down version.
Mario and to some extent Zelda has as well. Though not the lock and key item style of Zelda, more the room to room mayhem.
I think this old game would make a great RL. Note it is real time, a maze shooter, but the speed of the game makes it all together different than the hectic arena style twin stick shooters we've seen so far.
Night Stalker (it's the pacing here. Just great. Only one screen. The bats/spider only stun you. Robots get harder and hard.)
http://www.youtube.com/watch?v=UaqbN480WogSimilar games of note:
Berzerk (one of the best designed games ever. I mean it. The Atari controller makes this game fantastic. Tons of boards, tons of AI variety for the time. Seems procedural.)
http://www.youtube.com/watch?v=Yej3M9Ec8CgMaze-a-tron (with the old forced scrolling push you forward mechanic. Could easily be procedurally generated. We've seen 7DRL's like this.)
http://www.youtube.com/watch?v=O_YnipBjta4