Great thread. It's really a challenge to fuse open-ended storytelling with narrative. With open-ended games, one choice can completely alter the direction of the story, forcing the developers to practically design another game in some cases.
The only way around the "create 1000 stories" model is to create an intelligent world; one that can rationalize the changes and choices made and alter the characters and setting appropriately. But this is really, really challenging.
I guess it's about finding the perfect number of branches to a story. Not to few, but not too many.