For me it's not a thing that doesn't exist, but it's pretty rare ! I'd like a storyline (no game style in paticular) where the player's actions really matter.
And I don't mean that it would define different endings, but as you progress through the storyline, the environment changes, the npc's reaction's aren't the same, etc.
It has appeared in recent games (Skyrim, Dishonored, Mass Effect for example) but it's still too rare in my opinion !