For Sandbox games, I have found the following elements to be important:
1) Since it is open architecture, there are encounters within the boundaries that may be too much for the PCs to handle at first. This was pretty common in the
oooooooold Judges Guild wilderness adventures.
Be Careful! IME, a lot of players expect every encounter to be winnable/solvable with current party resources, and may not run/retreat/avoid when that would be best. That's how you get TPKs. Try to make sure that you give your players ample hints when they are really about to engage with something out of their league.
2) Demand PC histories for each PC- give out "carrots" for particularly good ones. They will give you plenty of plot hooks and insight into PC/Player mentalities.
3) Find a way to keep the campaign's rumor mill going. Back in the 1990s, I used an "Agency Memo Sheet" for a 1900's Wellsian/Vernian superheroic campaign that had blurbs or detailed news of the world ("Riots on Mars!" "Museum Attacked by Mer-Men!" "Ship Destroyed by Bolt of Light off Coast of China!") and the accomplishments of other agents ("Super-Powered Indian Sympathizers Arrested!"). I left it posted on our host's corkboard, so people could check it out any time they wanted (nowadays, I'd just send out an email, have a Yahoo group or some such).
The blurbs stimulated the players' imaginations, and they often discussed the rumors as we were setting up, or even speculated about them in game. Essentially, I turned my players into an idea factory that prevented me from ev
er experiencing writer's block for the campaign's entire multiyear run. Sometimes, the players thought they had guessed right about some rumor or another, not realizing that, in fact, their table-talk inspired me to add something to the campaign.
What do you do when, in the middle of the session, the PCs start heading for Whatzisnehm's lair but you don't have any encounters statted out?
1) A region by region random encounter chart is your friend, and remember that you can have a set of stats and call them anything you want- last session's band of Human brigands who struck from ambush can quickly become Orcish mercenaries who are running from a battle they were on the losing side of.
2) Load up on some of the little mini-adventures out there, be they mini-modules or locales published in Dragon or some other magazine.