Looking for an article idea to finish this week off with, I went trolling through the suggestion pot. The most recent question caught my eye.
Crushnaut asks: "I would like to work a rival, or reoccurring adversary into the next campaign I run. How do you guys work these into your stories? Do you use the powerful, yet utterly hopeless defiler as seen on TV? Or do you use a truly threatening foe?
What if, to your best efforts, the PCs kill their nemesis before you are ready for that dramatic final show down?
Do you find rivals and reoccurring villains to be an effective way to add that extra something-something to a campaign? "
I’m going to go ahead and answer the last question first. Yes, yes, yes, hell yes. The most memorable games that I’ve ever run have revolved around the recurring villains. I merely have to mention the name "Lealia Bellemar" or play the song "Whatever Lola Wants" to one of my players to get him to shudder and glare at me. Mentioning that I might bring back "The Master" for a session will make most of my players cuss and talk about how there is no way he could be alive as their previous characters burned the body and buried the ashes in various consecrated grounds. This didn’t need done, they just hated him. Recurring villains are a great way to give the party reason behind the myriad adventures that we as Game Masters throw at them.
Since Crushnaut asked how we did villains, I proposed the question to all the other gnomes at the latest Gnome Meeting/Rocket Bike Race/Volleyball Game/Dinner Theatre/Crimp-off.  Here are some of the other gnomes answers before I go ranting away.
Kurt "Telas" Schneider
Make sure they have an obvious exit strategy, and then a second, not-so-obvious strategy. Because players like to smash GM dreams…
Give them some depth to their character. One-dimensional villains aren’t as memorable.
It isn’t about the actual villain, but the villain’s cause. Give them a
reason to be the antagonist. This way if the PCs bamboozle you and
kill the villain (more like when the PCs bamboozle you) the cause
lives on. You can promote the next villain in line to lead the charge.
Don’t let the PCs get in striking distance of the Villain very often. Use henchmen, proxies, etc. Often PC’s are pretty crafty about how to finish off a Villain once they get physically close, so keep them at arms length. My typical formula is to have an early encounter with the Villain when the PC’s are not in a position to do any serious harm. Then the Villain goes away, and I move on with other stories. Then the Villain sends some henchmen after the PC’s, reminding them that he is out there. That often starts to open up what the Villain’s real goal is.
Also, make your Villain as smart as your PC’s. In D&D, a powerful Villain already has some protection from the Scry & Burn tactics the players thinking of. They use henchmen to learn about the PCs; to discover that the Mage loves lightning bolt, so when the Villain encounters them next, you know he has protection from lightning.
Also I like my Villains to go after things that the players hold dear. Burn the Druids grove down, kill a few family members, raze that town they like to visit after adventures. Make it personal, without directly attacking them. The more personal you make it, the more they will love going after them.
Finally, at some point you have to give them the Villain to kill. After all that harassing, the players will reach a point where they will have no other goal that they want to pursue more than killing the Villain. At that point, you must arrange the final battle.
A Villain is More Than An Enemy, A Villain Has A Plan
This is always rule #1 for me. A villain is something special. They are more than just someone that is an enemy to the group and they are definitely more than just a combat opportunity. Like Patrick mentioned, a villain has a cause. The villain and his/her/its motivations are key to the entire game. The game where the Big Bad Evil Guy is a megalomaniacal genius trying to take over the world is incredibly different than the game where the BBEG is an entity from outer space looking to destroy the planet for energy.
No matter what game you are playing or what type of villain you are using, make it one of the most detailed things about your game. Know the villains motivations and their methods. Know how they work and what their plan is. This will be essential to recovering from any monkey wrenches the players throw your way. If the villain needs a power source to fuel his death ray, but his henchmen get thwarted stealing it, then the villain will probably go looking for a backup source. Knowing the motivation and the method of the villain will help you stay on track with what you throw against the PCs.
Villains Are People Too
One thing to remember about Villains is that they are people too. They have pasts and histories just like PCs do. They have mundane things in their past and they have a reason for doing the evil things that they are doing. These are all factors you should include with a recurring villain. I always make sure that my main villain, and their lieutenants, are written up as full PCs with backgrounds and histories. Even if those never come up in the game, I like to know who the villain is. I heard an interview with a novelist who said that he filled out job applications for each one of his characters . It helped to flesh out who the character was. While I’ve never done that, it is a great idea.
Villains Need To Be A Good Rival To The PCs
While villains are their own people, they also need to be a good rival for the PCs. If the PCs are fighting Harvey the Evil Hamster of Doom as fantasy heroes, it just doesn’t fit. Imagine the game as a movie and see if your villain would seem silly against the PCs. This doesn’t mean the villain has to be the perfect enemy to the PCs, not by a long shot. Think about the Joker Vs. Batman. By his description, the Joker just seems out of place next to the Dark Knight. However, when you look at the skills and specialties of the two, the rivalry makes sense. In most cases the Joker is portrayed as being as clever as Batman is. Where Batman is cold and logical, the Joker is a seemingly insane ball of energy and randomness. They are both ruthless and have an endless amount of dedication to their goals, but they work with different mediums. The point is that despite their differences they provide a competent match to each other.
Plan For Your Villains Defeat – But Not Too Soon
One of the questions that Crushnaut asks is about something that can come up very often: What if, to your best efforts, the PCs kill their nemesis before you are ready for that dramatic final show down?
When creating a villain, the moment that most Game Masters think of is their final conflict with the PCs. The place where the PCs defeat the villain and save the world/princess/city/kingdom/etc. If that moment is many many sessions in, then there is a lot of ground in which the PCs could prematurely exterminate the villain. If your villain doesn’t have the stamina to go the distance, it can be a big disappointment.
Phil and Kurt threw out some great answers to this problem. Like Phil said above: "You are going to have to give them a villain to kill." and "Don’t let the PCs get in striking distance of the Villain very often. ". Like Kurt said above: "Make sure they have an obvious exit strategy, and then a second, not-so-obvious strategy".
One thing I do is to stat the villain out so that they are a challenge for the level that I plan for the PCs to face him/her/it at. That way, even if the PCs do get into striking distance, they find themselves severely outclassed. After a vicious fight the villain will usually spare the PCs. This fuels the PCs righteous anger for the final confrontation, right after multiple sessions of side-quests to level grind.
I also tend to give my villains multiple lieutenants which may or may not be faced by the PCs. This lets the PCs get a sense of victory at certain points in the campaign while still saving my major villain for the final conflict.
Villains Have Been Defined In Many Other Media, Make Use Of What Is Already Available, Then Modify It To Fit Your Game
One final piece of advice from me. Villains of all varieties and demeanors have been detailed in other media. Watch movies for great villain archetypes. Play videogames and see the various ways they portray their Big Bad Evil Guys getting away from the first encounter with the heroes. Read picaroon romances, hardcore sci-fi, comic books, spaghetti western, and any other kind of good guy/bad guy literature you can get your hands on.
Take examples from anyplace you can find them and modify them to fit your game. While the over the top "Starscream Escape " might be too much for your campaign, the concept behind it might find a proper execution with some tweaks. TV Tropes  is a great place to start picking out examples of these kinds of ideas.
So what kind of villains do you usually use in your games? How do you handle the PCs first encounter with them? What are some villains that make you shudder to this day?