That doesn't sound like a sandbox. It sounds closer to
No Myth.
A strength of No Myth over sandboxing is that the setting is guaranteed to be responsive to the interests and concerns demonstrated by the players. In that way it is very player driven. But for some players, of course, this is a weakness rather than a strength, because they want a gameworld that is "real" and exists as an object of exploration independent of their interests and desires. For those players, traditional sandboxing is preferable.
(You seem to allude to this desire, by some players, for a "real" gameworld when you say "I don't think the players ever thought I was making it up at the spot.")
Ok, first off, cool link. My players would be fine with a no-myth type of game, and it sounds like a good way of running a game that feels far from railroady.
Secondly, I was trying to more or less procedurally generate the content as the PC's acted. Usually I find this really hard and it shines through that the material isn't prepared, but in this instance, I think I pulled it off really well. So well that to the players it felt like the characters were playing in a simulation, not a pre-made adventure. It felt really good, because I wasn't nudging the players in the direction the session went at all, this very important part of session of the campaign was completely player-driven. And the players could feel smart about their little assassination.
I think that when you run a game where the players know that clever ideas will make life easier for them creates a game full of clever ideas and awesome failed plans. A typical adventure path really cuts down on this because as a player, you know the DM is running a pre-made story which often only has one ending. Coming up with something clever isn't something you really bother with, because, hey, it's going to end the same way no matter what you do (as long as your character survies).
I think one very important part of a RPG is that failure should always be an option.
Anyway, and a bit more on-topic: I do think that the sandbox-railroad is two extremes you seldom run into. Most of the time you are somewhere in between. Personally, I am much more happy when I am far from a railroad, but at the same time, I do like story.
My way of running a game is usually for me to have an idea for a game, get the players on board with that idea, come up with some suitable characters/backstories/motivations, line up some events/npc's with motivations etc and go from there. The first few sessions are usually a bit railroady, but I try not to prepare too far in advance, so I can take into how the game world would react to the players actions.
In one session, I had a secret staging camp for an invasion planned with a map, who were in it and their general motivations and connections to other NPCs. I didn't plan any encounters or anything like that. To me, that's the job of the PCs - to make as easy encounters they can. In this case it went really well, one part of the party did some sneaking/assassinations, while the other part just walked up to the NPCs and just bluffing their way out, using their acquired, but unconfirmed knowledge of the secret NPC connections. The fun part of it was the way the PCs formulated themselves. They got confirmation of the connection, and made the bluff a whole lot easier. Clever!
Anyway, the above example is one way to prepare in a more sandboxy, not-railroady way. Instead of preparing encounters, prepare sites/situations where you don't take into account what you think the players will do (but possibly what the NPCs know about the PCs). Then let the PCs interact with the site/situation and generate your encounters from that. In the example above, I got a stealth-encounter, a skirmish and a social encounter out of it.