I like nonlinear games likes deus ex and SWKOTOR, but I can't really find any game where the decisions you make affect the story 100%. With the two aforementioned games, it seems that they have a very specific story and you have options about various ways to approach problems, but you get the same problems and story each time.
I'm talking about a game where if you kill a certain person (or some other thing) the story movies in an entirely new direction.