Edit. My own theory, which I just remembered by re-reading the Paizo discussion is this: Hex-crawling brings wilderness adventures to the game table. 4E has been extremely poor at implementing this aspect. The wilderness skill challenge is fun maybe once or twice, but gets old soon - even when we factor in other exciting wilderness skill challenges (like the boat raft skill challenge in 'Journey through the the Silver Caves' which made it into DMG 2 - that's just brilliant all round).
If I am not mistaken, it is possible to have "dungeon sandboxes", too. But I still agree that more stuff in the wilderness would be cool.
In fact, in my online campaign, I think I've had not a single dungeon so far. It just never came up, and the story felt much more natural going on under free air. ("Offline" I am running the Hx/Px/Ex series, and those are dungeon heavy).
Not that I would want to describe my campaign as sandbox, but I think generally more city and more wilderness adventures would be my preference.
Not to start an SNG food fight, but I think that sandboxes really appeal to Simulationist gamers. The idea of the world running on its own, not waiting on the PCs.
But I don't see how that works; when folks here talk abotu sandboxes, it seems all the little things in the sandbox are just in a time stasis, their motives and goals just frozen until the PCs stumble across them. If it were a real world, all the things that happen would happen whether the PCs get involved or not, rather than just waiting for the PCs to walk up to them.
I would try to avoid "simulationism" and similar GNS terms for sandboxes. I think they are misleading and it seems to set up false conflicts. You end up trying to define a term with another term and then conclude that this doesn't work out. Maybe your initial assumptions is simply wrong. It's not about "simulationism".
There is one aspect of "immersion" - you can see and explore all the facets of the world - within the expected limitations. (Like not flying to locations that require a helicopter before you have a helicopter). You don't follow a specific plot line that is handed to you - you can choose any thread you find, or create your own. Of course there are other, practical metagame considerations (like the DM can't prepare a real, fully defined world for you, so some stuff will not be predefined and might not be "ready" for exploration).
Whether a sandbox is "static" in that only the PCs intervention can change things, or not, might be dependent on the DM. It might even be something "natural" for the situation, depending on how it is designed. Either way, it doesn't have to be a problem for the group itself, and it is still clearly distinct from an adventure path that the players have to follow.