As I've been stocking the Dark Country Wilderness map, I've been reminded of something that really impressed me about Rob Conley's Points of Light products. Each of the sandbox settings he provides in those books has a history. More interestingly, these histories are wed into the settlements, lairs, and ruins of that setting. A ruined castle isn't just a ruined castle; it was destroyed in the war that took place 50 years ago.
I think this sort of thing is necessary for a good sandbox campaign. I'm a huge fan of dungeons but I find them much more interesting if they have something special about them. Making a dungeon or ruin unique is quite easy if you have an idea of the possible causes of its creation. If these possible causes tie into the greater milieu of the setting, all the better.
Aside from making dungeons unique, it also helps to inform player decisions. If one wishes to conduct a West Marches style game, one easy way to inform players of the various sites the can explore is to place bits of history in various other dungeons. Maybe two sets of ruins on your campaign map were destroyed in the same war. You could place a map showing the various fortifications in the area at the time of the war in one or both of the dungeons. When the players find it, they now know the locations of some other possible places to get loot.
I think this works best if the DM creates multiple threads for the sandbox area. D&D settings are by and large old worlds. They have seen the rise and fall of many civilizations (and races), countless wars, and numerous natural disasters. The key is to not overload the area with these sorts of things. At some point if every single dungeon or ruin had a different catastrophic event lead to its creation they lose all since of grounding. A few broad threads are best because they tie locations together and make them unique at the same time.
One tangentially related idea can only be seen in long running campaigns. As PCs reach name level and begin to build dominions, they start to shape the history of the setting. Assuming you keep the same milieu for multiple campaigns, some of the dungeons future players might explore were built by previous ones. While this does not stress the importance of setting out the history of your campaign world, it does show how much more interesting a world that has a history is.
Needless to say I've taken this into account while thinking about the Dark Country. I will possibly do a post later on how I've implemented these ideas into my campaign design.