It's interesting that games, that are supposed to engage the users more than a purely visual media like movies due to the player interaction in the games, still suffer from the extremely linear storytelling that plague the more traditional media. At most players get to make small decisions with no direct impact on the main story, such as which weapon and way of approach to a puzzle. When players are given the choice of different responses in conversations with Non-playing characters (NPCs), the choice seldom matters, as the conversation almost inevitably leads to a predetermined conclusion.
The problem is quite obvious; the more options the player is given the more resources need to be spent on developing those options. At every branching of the storyline you'd need to spend twice as much resources on the parts after the branch (assuming the branch has only two options). Add another branching later on and you can easily end up using four times as much time and effort on a game with four different endings than a game with a single storyline and one ending. The choices speak for themselves, and for the most part, publishers see the economics of the situation.
One gameplay mechanism that could reduce (or hide) the linearity would be to, instead of giving the player for example, a number of different dialog choices to present to the NPC, you would instead give the player the ability to present various objects to the NPCs and receive pre-scripted comments. Of course there would be no way of knowing what objects would give the information necessary for progress (as well as requiring an incredible amount of info being coded about various items, as the number of interactible items would need to be quite big in order to create some sort of consistency). Though the risk of the system back-firing if the player can't find the correct item to present may be too big.