I'm interested in what constitutes exploration in your view. Does it have to be geographical?
Probably not, but I think that, in practice, it overwhelmingly is. The classic D&D sandbox is a campaign and/or dungeon map. The classic Traveller sandbox is a starsystem map.
My own game features a fair bit of exploration of history/myth - but because that stuff has, in the gameworld, already happened, I don't consider this a contributor to sandboxing. (And the background that hasn't yet emerged in play is always subject to revision in light of what is happening in play, in order to make it more interesting/relevant.) This exploration of backstory is more about the players (via their PCs) gradually building up a richer set of game elements to engage with in the course of play. It also tends to give play an increasingly epic feel as the campaign unfolds. It's a type of player/GM resource that informs situations and decisions - but is not itself a field of action.
As an exception to that last sentence, in my current game I'm also hoping to build up to heroquesting (or, in the language of The Plane Above, journeys into deep myth). But this won't be exploratory sandboxing - the heroquesting opportunities that arise will be driven by the narrative logic of what has come before.
When you are roleplaying an NPC, does that NPC tend to make optimal or rational decisions?
To link this question to exploration - while in principle it might be possible to run a sandbox where the emphasis is on exploring relationships between NPCs, in practice this is going to require a GM with the skills of a serious fiction writer, to keep all those personalities distinct and in coherent relationships with one another. A lot of people criticised the 4e DMG for saying that stereotypes are best for giving personalities to NPCs - but in practice anything much beyond this is an overwhelming challenge. Even professional script writers for long-running TV shows have trouble maintaining coherent characterisation outside the boundaries of stereotype.
My own approach to running NPCs is therefore closer to (although not fully) No Myth. A few basic ideas about history, allegiance, personality etc but then I just respond to what the PCs say and do, as mediated by their dice rolls. Sometimes NPCs will take decisions that look objectively irrational (eg if they're successfully intimidated by PCs who, in fact, they could probably defeat in physical conflict) but whether or not they're irrational relative to the NPCs subjective desires is a bit hard to judge, because my prior account of those desires is likely to be fairly sketchy.
Is there some cumulative effect of 'random' encounters which over time must produce a different game to one which is solely improvised?
When running Rolemaster I use random encounters and random reactions for the same sort of reasons that The Shaman has given in his response to this question, and that Ariosto gives as his third reason.
Running 4e, I don't randomise encounters - because the prep demands are too severe - and instead of randomised reactions, I use the unfolding results of skill challenge resolution to introduce the element of surprise/lack-of-predetermination.
Now, a prior map of possible events has branches. When it gets pretty complex, what does it resemble? It resembles a pretty decent dungeon map!
One difference between the sort of open-ended game I like to run, and dungeon, is that in a dungeon the map is known to the GM in advance. The players explore it. In my game, the event-map isn't known in advance. So it is not explored. Rather, in the course of play it is created. This is another way in which my game has some resemblance to No Myth play rather than (what I think of as) a sandbox.