Star Ocean: The Second Story is yet another example of an RPG that does this; it has 70-80 endings, many forking paths including mutually exclusive party member choices, relationships between characters, etc. The trick for making it feasible seems to be to make the ending modular so that it includes/removes different cutscenes based on what happened before. As I understand it there are quite a few old-school RPGs that do this.
Of course it is harder if you are talking about voice acting and super-detailed 3D assets. But assets aren't that hard considering you already made most of them for the rest of the game, and realistic voice synthesis is perhaps not that far away. So I don't think most people were expecting model (B), but even that could be viable if you controlled the number of forks carefully.
You can't build this (story goes down):
and so on and so on.The problem is, no matter how you disguise it, gamers sense in the first case that they're on some sort of rails. Then companies promise the second, whether they mean to or not. But they can't deliver across one game. I remember thinking when I heard the announcement about the Mass Effect trilogy laughing at the idea that they could do it across three. You just can't let the combinatorics explode that much and make decisions that change the story. (Note things like "whether or not a Krogan squad is there" are consequences, yes, but you'll note they do not impact the future flow of the story, so they don't contribute to a combinatorial explosion. It's a linear contribution; you have to model the event and voice act it, etc., but it's still just two story nodes not significantly interacting with anything else.)
Fallout 1 & Fallout 2 were structured as several parallel instances of the first example, which is probably the best compromise you can make to prevent exponential explosion while still giving some heft to the choices.
But ultimately, if you want your "choices to matter", you'd better stick to "classic" roleplaying. A Dungeon Master can react to your unexpected choices and set you in a standard "fetch the thing" quest but then react to you actually accidentally literally destroying the world when that wasn't written into their "plan", and then carry on with the resulting consequences if you like. Computer games are still a long, long ways away from anything like this: https://www.youtube.com/watch?v=1H-1WJtuzPg