How do you play Winter Tales (in a non-gamist manner)?
This meant that the last few players could always tell their story and
  weave in just enough story cards to win the quest.
  
  The rule about the active player being allowed to throw in one (and
  only one) last story card to wrap up the story likewise seemed
  useless, since one story card would never be able to impact the
  results anyway.


You seem to contradict yourself here. If one side has used "just enough" story cards to win, then a single final card should be able to tip the balance in favor of the active player's faction.

Of course, then the other faction has to account for this, and use "just enough plus a little more", to the point that the active player's likely plays would be balanced out, on average. Then, assuming everyone plays optimally, the deciding factor is the random selection of cards, and you are back to it being purely a randomly decided storytelling game, as intended.