The best villains are those that are tied to the PCs personally. There is nothing quite as gratifying as having the paladin break into the temple of hextor and interrupt the sacrifices, confronting the six armed iron monstrosity that the PCs have been hearing about in hushed whispers. Only to have it take off its mask to reveal that its the paladin's brother. (Incidentally, 6 poisoned attacks per round and ridiculously high AC is rather nasty to deal with)
Great villains have build up, having the PCs already informed through contradictory rumors about how terrifying and powerful the villain is makes the fight all the more intense. Oh, and mind control magic, pitting the PCs against each other is also fun :-P .