There are several degrees of sandbox campaign, and recently I've been leaning towards closed, objective based and beatable type of it. I always said, that sandbox stands much higher than arbitral improvisation game, because there are random tables and special referee tools, but it can't be denied that there is huge amount of improvisation, and it doesn't even decrease necessary prep. It's really hard for GMs to prepare, to make something good from poor random results rolled during play, so I've been looking towards something easier. Lost City of Barakus is great example of closed sandbox, where 90% is non-random, semi-linear adventure but in modular and sandboxy dynamic. And the rest 10% are also superb random encounters that are also quite developed. This is important too. When you roll minor curio on random tables, it often doesn't bring any value to gameplay. Anyway, the middle tier of sandbox is campaign where plot is open and in draft form, for example you've got villain's actions planned, but there is no predetermined finale, it depends on actions of PCs. It is interesting, but hard to do in practice without prepared locales and modules.
Then we've got full sandbox. But in this article I will discuss only one aspect of it, which is hexcrawl, and will leave out for now the case of dynamic plot development from random tables and PCs actions.
When I tried to run hexcrawl modules it turned out to be rather poor experience for both referee and players. When I read such module, I find it impossible to brew any sense out of these encounter areas and NPCs. They exist in separation from one another. Trying to bring some plot and sense only gave absurd results. After collecting my experiences I can point out following reasons on why hexcrawl is bad.
1. Each encounter is separated from others.
Even when you struggle to reference one encounter to nearby settlements or plots it still is small encounter, not worthy calling it adventure, too short and poor to be satisfying. Recent versions of Blackmarsh do a lot of effort to create interactions between different hexes, which looks nice (though I'm not sure how it works in practice), but it is not enough. After you resolve interaction between two encounters, that's it.
To put it bluntly, hexcrawl encounters are like monster hotel dungeons, where each room contains creatures that are unrelated to monsters in another room or anything else in the gameworld.
2. Trash hexes abounds.
Trash hexes is term I use for minor curios, landmarks, meaningless NPCs that were created only because otherwise the sandbox would be "empty". Why do you need something as boring as several monster lairs? Because sandbox guide says so? It is very limiting aspect of this method of campaign creation that referee has to develop such things. When confronted with something like this I can even see how right are newschoolers who criticize sandbox gameplay for wasting a lot of time on low quality gameplay instead of skipping to interesting stuff.
3. It requires too much prep AND improvisation at the same time.
Now, we can come to constructive conclusions and solutions if we look at successful sandboxes. One example that right now I can remember is Barbarian Prince, more of a solo boardgame than RPG. It plays really good, there is no time for boredom, and why is that, despite the fact that there are no long adventures, only worldmap with encounters and scanty developed settlements? I think it's probably because it has really tight encounter system and stong focus on objective. The objective is to regain your castle before an extremely short time limit. Encounters are clearly defined with no room and need for improvisation, while at the same time delightfuly unpredictable, because each one has a lot of possible variation depending on dice rolls. Encounter with a merchant can gain you a follower, kill you, allow you to buy something, or reveal plot secret that will show you a shortcut to win a game. Generally there are no pre-made locations or encounters except the Castles, each is generated during play. So Barbarian Prince at first glance looks like a good example, but I'm not sure if this style of design translates well to an RPG.
So what to do, abandon hexcrawl style of campaign maps, or rather change them according to more successful versions of it? I can't yet answer that question, because a lot more modules would have to be analyzed. Instead I invite you to discussion on this subject.