So, I closed out my last post with this:
"Is the NPC an enemy or an ally? Will the players thwart his/her plans? These are the most important details of all, the events that drive the story, which is precisely why they are left for the players to decide with actions and dice."
There's an obvious problem with this: Give the players the freedom to control the narrative, and they'll do just that. OK, it's not really a problem; it's the whole point of RPGs. But let's say you spend four hours carefully crafting a worthy NPC adversary intended to face the PCs several times, with increasingly higher stakes, until all plot arcs lead up to an epic, climactic battle. . . only to have the NPC decisively defeated in the first encounter. The first instinct of a GM is to starting fudging rolls and statistics on the fly to prevent exactly what the players are trying to accomplish (i.e., victory), but nothing could be more destructive to an RPG.* This takes away all the reasons to play an RPG and replaces them with a cliche, inflexible story. Still, the NPC represented a significant source of campaign material; it's not a desire to punish the PCs as much as that desperate sense of loss that tempts GMs to script the game. So, what do you do? Well, in this situation about the only option is to be honest, congratulate the players, and either try to come up with more material on the fly or prematurely end the session. The players might experience the disappointment of an anticlimax, but it's far better than sensing futility. The PCs might get access to a significant amount of loot far sooner than you expected, but you can always make the next encounter more challenging.
That said, the best solution is to avoid cornering yourself in the first place, hence the reason for this post. First, you shouldn't spend more than an hour (two, at most) on anything specific, because the players can always surprise you with their ability to destroy or disregard your prized creations. Second, it's generally wise to not put all your campaign eggs in one basket. If you insist on crafting a narrative where all evil deeds in a region can be traced to a single Big, Bad Evil Guy (BBEG), then it's probably best to avoid that early confrontation. (Don't make anything impossible, but you can certainly control the information -- if the PCs start out knowing nothing about the BBEG, including its existence, then they've got a lot of investigating -- adventuring -- to do before they can even point any sharp things in the right direction.) Personally, I like to create two, three, or even four potential adversaries with various backgrounds, personalities and methods. Note the word, "potential". The adversarial NPCs can certainly be evil, but they don't necessarily work together or wind up fighting the PCs. The last time I DM-ed (a depressingly long time ago), for example, the adventure included a manipulative priestess and a cynical politician in addition to the conventional BBEG. The PCs wound up killing two of them and never fought the priestess at all.
Perceptive readers (assuming I have readers) will notice at this point that all I've really done is avoid a problem by dramatically changing the formula. This can be restrictive; not every adventure should be a tangled web of interactions. Sometimes an adventure calls for a single adversary to focus on. How does one balance the simplicity of a single BBEG with the risk the players will prematurely blow up the story? This leads me to the second part of this post: scoping.
In the context of an RPG, by "scoping" I refer to the GM's conscious (or perhaps unconscious) sense of how relevant the PCs are to a region of particular size. In other words, the BBEG will only be as important as the PCs are to society. If the BBEG dies, that only means the PCs have become more important. Aside from more obvious bad habits and tone, this more than anything can determine a GM's particular "style", from "Monty Haul" to "gutter punk". Some GMs think the world is static; that heroes make for fun tales but aren't particularly influential. A "hero" in this context would be something like the Prince in a fairy tale who slays a dragon to rescue the Princess. A fun story, sure, but not meaningful. The dragon's role is illogically circular (I'm an enemy because I guard the Princess; I guard the Princess because I'm an enemy) and the Princess is just a trophy. The Prince starts out as royalty so there isn't any shake-up of the social order, either. At the other extreme, some GMs think heroes exist to change the world; some D&D campaigns even end with the PCs becoming gods. Of course, there is a very wide and well-populated spectrum in between; also, the setting and characters are key factors. As long as a street samurai spends his money on cyberware upgrades instead of shares of Berkshire Hathaway, PCs can't do much more than replace one cynical power broker with another in even the most optimistic Shadowrun campaigns. In general terms, though, I offer my particular take below. It applies to D&D, but this is carries over into other systems & genres quite easily -- in a modern context, for instance, replace "Emperor" with "CEO of multinational corporation". The usual exceptions apply; for example, if a village happens to contain a retired, high-level adventurer, then all bets are off:
1st-2nd Level: Social relevance is strictly a matter of background. Someone with noble blood might be acknowledged as nobility; a wizard will be feared by those who fear magic and a fighter will be at least "middle class" if only because his/her equipment is worth more than what a peasant could earn in several years. However, the key distinction is that the PCs will not be respected. They are unknown and untested; thus their names wouldn't be remembered by even the most isolated farmer. A druid would be indistinguishable from a hermit (unless s/he flaunts magic, which will set off whatever is the standard reaction to magic in the campaign); a fighter is just another mercenary. They might draw the attention of a village leader if only because even a 1st-level party represents firepower a small village should be concerned with, but in any decent-sized town, the party might as well not exist.
3rd-4th level: Local recognition. They can demand to see the leader of any village without notice and can possibly throw their weight around in smaller towns. The latter depends on the town's economic and political significance. A well-supplied, battle-tested town should still have the means to make the PCs behave themselves without even bothering to inform the Captain of the Guard; small and/or impoverished communities will eye the PCs as either a serious threat or a key to salvation. Within a city, the party still won't make waves bigger than what will influence a neighborhood or small community.
5th-7th level: Regional recognition. When they enter any village without active efforts to be subtle, it's a once-a-decade event for the locals. They can easily disrupt the economy just with their purchasing power, so reactions will range from exhilaration to terror. If anything, keeping a low profile in a village will take some effort. Even a small town might allocate all their resources to defeating a mid-level party and still lose, so they will draw the full, constant attention of such a town's leaders from the moment they arrive until well after they leave. In cities, PCs at this level will be well-known within any neighborhoods they frequent. Organizations the PCs have interacted with, even indirectly, will spread word within their communities of at least the PCs' existence and local relevance. At this point the PCs should be somewhat famous; some towns will hear of them before they even visit for the first time. The warrior of the group could probably defeat the local Champion in a duel (assuming the warrior isn't already the Champion), so whether the Lord is benevolent or malicious, the party will be handled with care. Their names may have even been mentioned to the King or Queen, making an audience with them possible with sufficient notice and/or justification.
8th-10th level: A party of this level or higher gracing a village or small town with their presence, assuming the community doesn't have a reason to know the PCs intimately, is a once-in-a-lifetime event. For small communities the PCs may as well be gods, in the sense that how they are treated is entirely up to the players. If they want to be worshipped they can probably bend an entire town to their will; if they want to be ignored they'll have the means to make that happen. In outlying (less stable) lands, the PCs' mere existence is enough to make the local ruler's grip on power feel perilously fragile; this influence on the balance of power will earn the fear of regional rulers and the attention of the King. Major organizations will dedicate significant resources to constantly observe, thwart or assist the PCs' plans. Even prominent Lords, mayors of large cities and minor Kings will be forced to clear their schedules if the party expresses interest in an audience. Only powerful kingdoms, cultural capitals (think Florence, Italy during the Renaissance) and empires would still consider the PCs well within their ability to control. Unless the party has spent their entire careers crawling through dungeons, no one in the kingdom has an excuse to not know their names. Otherwise, every town that isn't completely isolated will be buzzing with tales (with varying levels of accuracy) of their deeds.
11th-14th level: Most mortals are unable to comprehend, let alone assess, high-level characters' limits of power. The line between rumor and myth starts to blur in their minds. By this level, the party is not bound by conventional social structures. Unless they've actively labored to prevent it, they are living legends known throughout the campaign setting. A small group can never manage a kingdom by themselves -- at some point, magic is no substitute for bureaucracy -- but the key point here is that no amount of resources even an empire can bring to bear can exert any meaningful influence on the PCs' decisions. No spy can avoid their detection, no fortune can bribe them, no fortification can stop them, no army can threaten them. It would take someone wielding comparable power to pose a threat, but any such individual is the de facto power behind the throne, if not sitting on the throne already. Actually, the PCs' interest in mortal affairs ought to be waning. This is not a bad time to retire characters if they've outgrown the campaign setting, but if there's something left for them to do, their role in society is entirely up to them -- they can be that village hero-in-hermit's clothing or overthrow the mightiest empire at the height of its power.
15th level and up: The last sentence of the prior range applies; in fact, the cut-off is arbitrary and ambiguous. It can happen as early as 13th level or as late as 16th, but at this point the party should be so wealthy and powerful that it would be difficult to not be socially disruptive. They have the money to buy any business they patronize, and even the most powerful organizations' plan for dealing with the PCs boils down to either "stay on their good side" or "don't draw their attention at all". In that sense, they're now gods in the eyes of even the most arrogant mortals. The frontier for the PCs should be other worlds inhabited by more powerful and alien societies.
So, what does all this have to do with the "PCs killed mah BBEG" dilemma? Everything! The above applies to villains just as much as PCs. Getting a grip on the PCs' role in society should precede work on any NPC, because (with some very carefully measured exceptions) the PCs should never be interacting with anyone more important than themselves. If high-level characters are asked to save a village, the GM really ought to provide more compelling reasons than altruism alone, but this isn't a disaster. However, considering 1st-level adventurers would have problems with a family of robbers, a low-level BBEG shouldn't be some risk to end the world itself. As such, low-level characters shouldn't get a chance to kill a high-value target because they'll be too insignificant for such an individual to have a reason to be in the area in the first place. This mitigates the effect of a BBEG's premature defeat because it's less about its power and more about its importance. A low-level villain may have ambitions to take over the world, but the feasibilty of such plans should be more comical than dramatic. And if the PCs somehow manage to kill what was supposed to be a recurring BBEG? Move them up! If they've outgrown the village, draw them to the town, where more worthy challenges lurk. This is the "BBEG Staircase". There is nothing wrong with early social advancement as long as the pattern itself isn't broken. So, OK, if the PCs have already brought an Emperor to his knees by 3rd level, you might want to start over. Otherwise, move them up; the above is intended to be highly flexible and dependent on context. A group of 4th-level adventurers gaining notoriety in a moderately prosperous town wouldn't be unheard of, but their arrival in the city will be greeted by a fresh set of doubters. They'd need to prove themselves all over again, but on a grander stage with higher stakes.
While the BBEG's role is closely linked to the campaign scope because RPGs are inherently full of conflict, keep in mind the other details. I've (figuratively) seen royalty roll out welcoming carpets for low-level characters in some campaigns, high-level characters haggling over basic equipment in others. It's strange how the influence of the PCs in the campaign setting is misapplied even within a social context the entire group takes for granted. The role of the BBEG is just another indication of whether the PCs are properly scoped.
*This was, in fact, the major flaw in the "Dragons of Faith" module I mentioned previously; it meticulously decided not only which NPCs die, but when -- doing almost anything out of order was catastrophic to the plot.