A game I equally loved and hated for having multiple ways the story could go was KGB. Sometimes you would lose because of a decision you made hours ago. :D
Adventure / Point-and-Click / Narrative Games
A community for fans, devs, and general aficionados of the adventure game genre. This includes IF/parser games, point-and-click games, puzzle games, walking simulators, and whatever else you want to call these. To us, they're simply adventure games.
King's Quest 6 fits the bill for me. I love that there's not really some dialogue choice that puts you down a different path, but just basic game choices make things play out in different ways.
Even if it doesn't change the overall story, I love it when there are multiple solutions to puzzles. It's at least altering how the story plays out and makes it more tailored to the person playing it. Even crap like the two ways to handle Orat and the start of the Deltaur in the first Space Quest has always been fascinating to me.
Honorable mention to how the RPG mechanics in Quest For Glory and Heroine's Quest alter how those stories play out.
Might not be what you were looking for. As someone who doesn't rank stories that high as being important to her adventure gaming, I did my best.
Conquests of the Longbow: The Legend of Robin Hood is short but does this excellently. Instead of dead-ending you, failure usually only makes the ending worse.