People with high social standing and/or entangling alliences and people under their thumb. Combined it makes them largely untouchable because even if people believe that they would commit some evil act, the consequences of turning them in or killing them would be as bad or worse as doing nothing to them.
People you never suspect as being a suspect, usually this works best in claustraphobic environments. (Such as when I had my PC's and others trapped in Pandemonium with planeshift failing on them and someone or something out there in the darkness killing them when they sleep, etc. Looks on their faces when they found out who it was were priceless.)
People with whom you know there's something odd or wrong about them, but there's literally no evidence to prove it. Something about them strikes you wrong, but on the surface there's nothing to see, and their history reads as blank as a dead man's brain waves.
Several of my more overt villains have inspired loathing on the part of both PC's and players alike. And a combination of that mystery and untouchable status with overt blinding evil can work as well. At least one of the longterm villains in my current campaign is a newly risen Oinoloth by the name of Vorkannis the Ebon. His history is a blank spot, he simply walked out of the hinterlands of the Waste and rose to power like being hurled from a slingshot to the top of Khin-Oin. It's that mystery (and suspicion that he's not a Yugoloth) with other campaign elements that have fallen into place over the course of a year long game that make him a memorable creation.
I like villains that have a LONG setup. I don't like one shot villains. A recurrant enemy is a respected one.
