I'm running a quasi-sandbox D&D 4E campaign right now. I use the term "quasi" because I don't have an elaborate map of the city of Grimfest, where the campaign is largely located. What I do have is a running tally of multiple quests, anywhere from three to seven on average, that the PC's can tackle. So before each session the players tend to email each other saying things like, "hey, those ogres are continuing to hassle the outlying farms around Grimfest, but I really want to return this statue to its rightful place at the temple of Eternal Dawn."
The Icicle Club, a private club for the wealthy and decadent of Grimfest that also serves as the hunting ground for a group of vampires led by a Baelnorn Lich, has been the most engaging of locales. Earlier the group had infiltrated the club and discovered the lich's presence (also, on the side, destroying a few of the master vampires that make up the lich's inner circle).
Last night the players realized that they would have everyone showing up for the session (a rarity) including the avenger PC with his radiant-based attacks and decided that they wanted to go after the lich. What followed represented almost a "leveling up" of the campaign, rather than the PC's. They used their stealthy PC's to "stake out" the club, ambush vampires as they wandered out alone to hunt prey, contacted local thieves' guilds to find out about the security of the club and the possibility of underground entrances, and finally lured a vampire into a trap where it couldn't escape and interrogated him.
The assault on the club did not go so well, partially because the players forgot a small detail regarding entering the club that then triggered a trap. This is a tough call as a DM to make: four months of real time passed, but only about one month of game time. If the players' forget, is it your responsibility to remind them.
The upshot was that one of the PC's became petrified (as in turned to stone) after the initial encounter. That meant the PC's had to wait while a couple of the PC's tracked down a Restoration ritual to perform on him. That went badly, however (right in the lobby of the club, no less) and the PC nearly died from hp loss.
I feel like, if you're 12th level, and haven't had a single PC die, then maybe the campaign's been a little soft, but that's just me.
Flash forward ahead. The PC's battle the lich. It's late, we are all exhausted but we're plodding along. I had a get-a-way planned for the lich beyond his simple phylactery restoration, but near the end I realized a PC was standing near it. He teleported over, dominated her, and then they both went through the extra-planar portal, and we stopped there.
Suddenly, we've got an honest-to-God archvillain for the campaign. A reoccurring character with a name and there is no question what the next quest is going to be. And I get to try my hand at both extra-planar adventuring and making up a good multiple-encounter location for the lich to be stashing his "bride."