I saw a recent video for Shadows of Mordor, and something about it has me very excited. That this is the Nemesis system it is going to have. More or less, certain NPC enemies will dynamically become recurring enemies, bearing the scars of previous conflicts with them when you face them again. This seems absolutely awesome, and it has some immersion that many modern games lack.
I think that games are moving more and more to dynamic, player-driven stories. Procedurally generated maps and enemies are already a common thing, so making NPCs that way too isn't that much more difficult (depending on the complexity of the system). I think we could be approaching a time where a game is little more than a loose setting, and the rest is generated on the fly as the player interacts with the world.
This is much the way I DM my Dungeons and Dragons sessions. I have a general idea of where the campaign is going and I know the names and archetypes of the major players involved, but I certainly don't have all the details created. I give those out as they are needed, creating them and making notes as I go along. For example, if your party comes along some bandits robbing a caravan, and you never talk to the people in it, I don't have the wasted work of naming them and fleshing them out. However, I do know its a minor merchant from the nearby town, I just haven't given him a name. If I need an NPC that owes the party something in the future, nameless McMerchant is available, but I don't have to figure out his motivations until then. Similarly, if the party has no interest in the leaders of the local church, then they don't need to exist on paper. Later on, when they become central to some plot, then they can become fleshed out.
I also like reusing hooks I've dropped later on in the story. For example, if there are some odd markings on a tree somewhere in Adventure 1, then Adventure 5 might have them show up again, revealing that some monster has been in the area all along and they almost became its lunch many levels ago. I have had very positive feedback from players because of this, and they feel very immersed.
So how do we get this into a game? Well, I think we need a storage of things flagged as interesting or reusable. Then, when the game needs an NPC, for example, it looks at this list, and picks from it. It then fleshes the character out in more detail and introduces it into the story. Same thing for interesting details. Maybe flag something to randomly reappear later, and have an associated questline if it gets investigated. Something like the aforementioned marking. If the player investigates it, he might eventually come across some fel beast.
In this way, you can have enemies that you don't quite completely kill off come back to ruin your life, and maybe those that you let live will see the error of their ways instead, and become a force of good. I can see a lot of potential, but the system would have to be carefully created.