It of necessity is a pre-existing one, or else there can be no "non-story" or "wrong story" to distinguish from it and thereby entail the construction of "story-telling" mechanisms apart from mere role-playing.
I honestly haven't had any experience with story games that played out that way. Did you see the example of Dinosaur Hruck? Scenes arise from questions like "why did this happen?" and "what happens when character X must confront choice Y?" The answers aren't predetermined. There is no "non-story" or "wrong story," there are simply many multiple possible stories, and you see which one is born from play. You only get a "non-story" if people don't play by the rules, or they quit early and go home without finishing the game.
If that sounds too much like "a roleplaying game", well, that's why I don't differentiate that much between the two in the first place. The goals can be different, but the process of "playing a game to see how things turn out" is similar at the core. Uncertainty is certainly an element in the story games my coworkers and I have messed with (hence the "game" aspect), it's just that there's a wider variety of assumptions that might be preset.
But I'll admit I haven't seen all the story games out there. Have you read any that set up mechanics for determining the ending ahead of time? I'll gladly confess that although I haven't seen any yet, that may just mean I haven't encountered the same ones as you have.
For me, the "Conan versus R.E. Howard" division in perception, powers and purpose is the clearest separation. Yes, Bob might sometimes imagine himself in Conan's place -- but does Conan ever imagine himself in Bob's? Does he make decisions based on considering himself a fictional "property"?
Either way, though, we're talking about Bob's decisions. Conan is ultimately Bob's creation, and Bob decides what he does, be it traveling to a fantasy version of a real-world culture Bob is interested in because Bob wants to write about that culture or making a rash decision because Bob can't honestly see him doing anything else. Story games aren't about the character understanding its place as a fictional creation, unless metafiction
is the genre, like the Game of Immortals we threw into a Changeling supplement. (And even then the True Fae don't think of themselves of fictional; they just believe that reality adheres to narrative rules because they can't imagine a world so random that it wouldn't. And in Arcadia, well, they're right. Faerie plays that way.)
Story games are all about characters behaving in believable fashion, and usually according to very detailed characterization — most I've encountered are based on the narrative conceits of pretty serious fiction, in which character decisions and consequences are more important than plot. The main difference is that the game may skip right to asking a player "What does Conan value more, his woman or his pride?" by setting up a situation in which he has to choose. The situation is chosen by "Bob," of course. The answer to the question, though, determines on how the game plays.