To some dude on page 2: I'm not a sandbox DM. My advice on "plots" is still relevant, but you will have to make it fit to your game, as per any advice.
to Ariosto: good points. I'd prefer you not refer to "old D&D" as that leads to edition bashing or something. You're main point about the dungeon level = difficulty = PC's choose to go deeper when they want to is good.
To snoweel: "epic story" is just as much if not more wish fulfillment. It is the players taking center stage of a big play, about them becoming victorious over evil.
Somebody else answered Lost's question about the Necromancer plot and the lumber business plot very well. If the PC's don't take initiative, you create a plot like the necromancer to drive them to action (because inaction will be very bad for them). If the PCs do finally see an opportunity (like the lumber business), you roll with that, and make threats to the business that keep them busy and happy. You don't destroy their business, but by makng threats to what they value, you engage them.
So if the PCs ignore the hook about the necromance, and get into this lumber business, you let the necro simmer, run some "threats" to the business" adventures. Then you bring the necromancer back as a "epic" threat to the business. You make it relevant to what they want to protect.
As Ariosto mentioned (can't believe I'm referencing Ariosto, we usually disagree on plot stuff), there are guidelines on what difficulty to make the bad guys if you're not doing the "sandbox" thing. Personally, I don't see why a sandbox has to be like a layerered dungeon where the danger goes up when it gets deeper. It can also be like Oblivion, where the NPCs are scaled to the level of the PC. But the point is, it can be whatever you need, and I define need as "whatever it takes to make a good game for the players."
Now one thing I see a hint of in some of the conversation, is the idea that there are "epic quest" story plots. As a DM, when you create the campaign, you might have some ideas of the mega evil the party is "going to face" eventually. I do not recommend actually planning this out or introducing it to the players at low level. You have no guarrantee the players or PCs you have now, will be there for the second half of the campaign where it actually matters.
Furthermore, the best way to "keep" players in their CR range is to make content relevant to that. They don't hear about the big high level problems because they're not high enough level to be connected to them via contacts and reputation. The party hears about problems in their range, an rumors of problems just above their range.
Let me approach this from another angle for a party not in a dungeon. This might also help relate it to sandbox play.
pre-adventure (or Act 1 Scene 1), the party exists in a static state. They have a strengths and weaknesses. They have whatever operations and resources going on. Let's say it's the party with the lumber business.
If the party hasn't really got a direction beyond that, you need to give them some stimulus. This will come in the form of threats or opportunities.
The party can probably only handle 1 active threat against them (I'm not talking a single encounter, I'm talking about a general adventure's worth of related problem and encounters to resolve it). Too many threats and the party will fail. The active threat will make the party react, which is a form of action.
If you want the party to be pro-active, you need to give them opportunities. Rumors, demonstrated weaknesses in their competition/rivals/enemies, etc. Basically stuff that makes the PCs think they could take advantage of it and advance themselves (not just XP-wise).
Where concurrent threats are best limited to a small number for game play purposes, opportunities can be limitless. Players don't really have a choice with a threat, if you don't deal with it, you're screwed. But opportunities are the real choices. Because players are free to choose or ignore them. This concept would probably help bring sandbox elements to a campaign.
The idea of opportunities is important. As a DM, you could make every entitiy a 20th char. This means the 1st level party has no real chance to advance or grow, because they can't solve anything because everything is significantly stronger than them. So a DM doesn't do that. They make a world with opportunities for the PCs to grow and expand. Stuff has weaknesses so the party can take advantage of them.
