Interesting. I was actually thinking about Tyrian as an example of a game where random level generation would work well (in contrast to those mentioned in my above comment), and wouldn't detract from nostalgia replay value. Another example would be X-COM. Both excellent games.