There are several methods that come to mind:
- The Spider's Web
- Run Away Badguy
- Sacrificial Minions
- Protected by Politics
Come to think of it, all of these are used by various Barsoomian villains.
The Spider's Web
The bad guy doesn't do his own dirty work. He coerces, cajoles, controls, and/or hires people to do it for him. This is especially useful if he's head of some organization with a livery or a common symbol, as players will connect the symbol or livery after a few mentions.
He might even be friendly to the PC's in person, and offer them help, and then have the help be sacrificed as his minions "underestimate" the PC's (in other words, a "balanced" encounter...).
Run Away Badguy
Not all badguys are willing to stick around and gloat until killed. Some will even have escape routes pre-set. The Runner Badguy will disengage, using special abilities and prepared escape routes with triggerable methods of delaying pursuit.
A personal favorite method of mine is a mirror of teleportation, inside a maze of mirrors, remembering the effects of darkness. Sure, you see him disappear... but there's more than one mirror, and they're one way.
If the badguy is in the city, he goes round a corner into a crowd and polymorphs... suddenly, no badguy, just a bunch of normal people. (And if they kill everyone, they will find they're considered the badguys later.)
Or, rather than Polymorph, he Dimension Doors into a doorless room. Possibly one beneath the streets.
This badguy type has minions galore when encountered. And they are psychotic, and love him very much. He need not run - he walks away, escorted by minions, while even more minions tackle the Players. This is, in D&D 3e/4e terms, time for a decidedly unballanced encounter with a bunch of mooks, but a considerable number of non-mooks. Aim for major threat, and let them escape if they choose, but not in the same direction. All the advice for how he gets away is the same as the Run Away Badguy, but players have to get through the minions to find out.
Protected By Politics
Make certain they know that the bad guy is a big somebody, and has powerful friends... like the Wizard's Guild's high council, and the local baron, and will be avenged. He can be hit, just not without major consequences... Consequences like being run out of town by the next shift of town watch and a half dozen spell casters. Better, this kind loves to gloat. And usually arranges to have witnesses to his potential demise. Eventually, he will get caught red handed... but that's often at the efforts of players (or protagonists) to reveal him to other trusted members of the court.
Protected by the Church
A special subset is clergy of the local dominant religion/cult. Pre-modern cultures are real keen on avenging dead clergy, and in fantasy worlds, the deities themselves might take exception. Especially if his hidey hole is the local cathedral.
The Spider Protected by Politics
This is the ultimate version of it. Not only does he have the Noble's ear, he's got his own organization, and doesn't do anything himself. And will praise the PC's for killing his minions...
Prince of Persia (the movie) is an excellent example of just such a villain at work.
The guy who's just too tough to take on. And too lazy and egotistical to bother killing the PC's. The problem with this guy is that, in a typical D&D game, if you stat it, they will kill it.
Usually, the pure tank just leaves them for dead; in D&D, that doesn't work so well, due to the "Fine until 0 HP, dying below that." So he usually combines with some other archetype, as well.
The Trapmaster simply has a zillion traps to trigger when attacked. And he leaves PC's in one, and assumes they're going to die. He's really not all that bright, but he's mechanically inclined.
Worse, many Tanks are also Trapmaster types. He beats on you, gets you to follow, and triggers the trap while you chase him. Then, he wanders off, assuming you're dead. Classic example is from the Le Guin novel, The Tombs of Atuan.
Many badguys combine two or more. Loads of fun to be had.
Cardinal Richelieu, in Dumas' The Three Musketeers, is a Spider protected by Politics, Runs Away a lot, thanks to his Sacrificial Minions.