I don't understand how certainty equals to the GM's novel. I totally agree that making your players characters in your story is a terrible way to GM, which is why I hate the term "Storyteller" to describe a GM. But to maintain a non-linear gameplay you really only need to ensure players are making their own choices. I don't think it really matters if what's over the mountain is either randomly generated or made up, because players really only care if there's some internal logic to what's there. If there's no internal logic, then the illusion will be broken no matter what. Simply, I have always found my judgement to be superior to what I can determine randomly, and frankly, it's just easier to think it up.
Okay, I think I understand what you are saying, and I'm in the same boat. It comes back down to that wretched term "random."
For instance, if the players walk into a city, a dragon can't just pop out of nowhere if there is no history of dragons nearby. Instead, when I'm letting the characters know about "Adventure hooks," I first observe the history of the location to see if it is a region that is strife filled or not. I then roll a dice which is modified with values based on that history to actually see if anything is worth mentioning beyond the setting descriptions (a peasant revolt, bandits in the woods, etc.) If the city has a whole slew of reasons to have bandits in the woods, it's much more likely that bandits will be there, rather than, say, a dragon popping out of no-where. So I generally create a small table of the variables in my head or on paper, assign them modifiers based on local history. If it turns out bandits are in the woods and the players investigate, I then repeat the process to determine what kind of bandits they are. If there happens to be a rival baron to the local duke, then it's going to be pretty probable that the local baron might be responsible. If there are nomadic, aggressive tribes nearby, there is a high likelihood that they are responsible.
So you see it's not actually random, per se. Yes, sometimes a dragon might appear out of nowhere because, yes, improbable things do sometimes happen (a young red dragon userped and sent flying to find new territory?)
I don't provide "story arcs." I instead just have a living world that goes about its business, and the players may take part if they'd like. The players are only limited by the physics of the world and the personalities of their characters, which they defined at the start of the campaign. Stories arise when players get involved with a specific place and specific people. If they clean out those bandits and the baron is responsible, then its likely they've found a new arch-villain, but if there were plenty of other possible sources of bandits in the area.
But I do insist that if there is no "constructive uncertainty" in the DM's decision making, the players end up spending a lot of time "guessing what the DM is thinking" whether they are good at avoiding metagaming or not.