The differing origin stories in Dragon Age: Origins is a decent idea, and well implemented, too bad that immediately after it becomes "now we have the set of quests that everybody gets".
The criminal or cop segment of NWN2 is a good idea but badly implemented (The thieves guild branch's storyline is just....bad...so it comes to a false choice) and then after that segment you're back to "and now the story that everybody experiences".
If you're going to choose, choose on the story not the people.
Okay, you chose to go help the siege, by the time you get back, the rumors of a haunted graveyard have blown up into a zombie uprising.
Okay, you chose to investigate the haunting, by the time you finish that the siege overcame that allied stronghold.
Pathfinder: Kingmaker does this a little bit with time-constraints on some stuff. I just wish it was less time constraints and more "you chose X, so Y is going to be unavailable/different".