To be honest, I don't think it's really the voice acting that's causing it. Sure, that'll be a factor. But I think that the main problem is the expectations people are putting on games.
We expect good graphics. We expect seamless and exciting gameplay. We expect awesome combat or deep, intriguing story-lines - or BOTH! We expect a complete lack of CTD's and various other failures.
And to top it all off? We expect that our choices will matter.
In a game like Mass Effect, they do an amazing job of giving you the ILLUSION of choice. SPOILER ALERT: You can save the Coucil or let 'em die. You can kill Wrex or talk him down. You can let the Blue Suns leader get away, or let the refinery blow up.But ultimately, you still end up visiting the three key story planets, doing exactly the same thing there, and finally saving the universe from the big evil nasty.
Similar thing in KotOR1/2. SPOILER ALERT: Regardless of whether you go Light or Dark, you'll still end up doing exactly the same thing. Charging up to the final boss and attempting to whoop up on him. Either Light) because the BIG EVIL NASTY(TM) needs to be stopped, or Dark) because you don't want the BIG EVIL NASTY(TM) to rule the universe before you can take it over. But at the end of the day, you're still whooping up on the big evil nasty.
The problem with real choice is that it branches. Never mind the multiple voice-acting required. It's the infinite branches that are a problem. Let's assume that each choice only has two possible outcomes (and we'd all whine if that was the case). After choice 1, there are two possibilities that need to be taken into account. After just 10 choices, there is a potential 1024 possibilities - some of which will be interrelated!
Using the example in the OP - If we sneak in, there isn't war. If we slaughter everything, there is war. If there is war, Kingy might give us a war-related mission. If there isn't war, he won't, he might give us some other mission. So now they have to program TWO missions - and only 50% of people will play each one. That may rise on second/third play-throughs, but I doubt it would get much higher than 65%. A few more decisions down the line, and you're into a situation where less than 10% of the gamers playing your game will ever see that mission. The cost/benefit is simply too low.
Currently, it simply isn't feasible to program for that sort of flexibility. You almost need an AI to act as GamesMaster within the scope of the world before that sort of thing becomes possible.
Until such time, we're going to be railroaded into fairly linear choices - no matter how good the illusion they disguise them with is.