Recurring villains are a highly desirable thing to have in your game. Quite a few of the most 'bad ass' moments I've heard about in game have been tied to the emotional punch of finally beating a recurring villain. The sense of history you can get with players and a recurring foil can be amazing. Unfortunately, it can also become a cheap, flimsy experience if you're not careful as the villain quickly goes from being a threat to a joke. Today I want to talk about that.
Cartoon Villain Syndrome
The problem you can have with recurring villains is what I call cartoon villain syndrome. This happens when the villain loses any feeling of being a threat because every time they run into the hero they lose and basically have to escape. Instead of being a challenge, they just become a thing to be dealt with. Instead of amping up the tension they become a nusiance in the vein of "oh, these guys again?"
Basically, everytime the player beats the villain - even if it is a close match - the villain loses some threat. Why? Because they become an overcome challenge, as opposed to something that was able to beat the players. Now, yes, if it is a very close fight that feeling won't come as fast, but it will come. You can only beat someone so many times by the skin of your teet before your brain reasons that the victory is due to superior skill/ability, and not due to something like luck.
Xanatos Gambits Only Go So Far
One of the common things I, and others, recommend to make villains feel more effective is to employ a Xanatos Gambit. A Xanatos Gambit (named after David Xanatos from Gargoyles) is a ploy where the villain does a plan where regardless of success or fail they get what they want. For example, in one episode Xanatos breaks a group out of prison to do jobs for him. The Gargoyles beat siad group, but the actual point of the plan was to get the person who refused to leave out of jail earlier because of good behavior.
Xanatos Gambits allow the villain to win even while the heroes also have the more immediate win. Basically, Heroes win the short term battle, villain wins the longer term objective. It can work for some villains to appear effective, but ultimately the villain still seems like less of a threat because they lost the direct confrontation. Sure they won, but only by using trickery and avoiding the heroes - sacrificing tokens in one arena to get something elsewhere.
The Villain Has To Win Sometimes
No, to be a threat the villain has to win sometimes. Until the villain is beaten they will remain a prime threat and someone the players are eager to take down. You can increase this feeling if the villain wins the first several encounters with the heroes - provided you're not wiping the party everytime - but you also need to be careful doing that that you don't make the PCs feel powerless.
After the PCs beat the villain you start having the Threat Decay. The second encounter after a first victory can still work. A third, fourth, or fifth encounter with each of the previous ones being PC wins will seem less and less impressive. The NPC just becomes a mook with better stats to beat. However, if the PCs win one encounter, than the villain wins one, and there is some back and forth you can have something else happen.
The villain won't be the giant, big, scary bad. They've been beaten, that feeling won't come back. However, you can get the feeling of a rival out of them. You can build a relationship - albeit an antagonistic one - with the PCs and use that to strengthen the game. If the villain can win and does win sometimes, the PCs have to recognize that.
How you make that happen is up to you. I don't recommend just blapping PCs to prove a point, but you can defeat them. Make them run away. Put them in bad positions but not let the villain finish them off on occasion (pre-cook the situations for that to happen.) Have fun with it. Just don't let your recurring villains be jokes...unless that's what you want them to be.