I know of a couple of tactics that worked really well on me a few years ago, and one that I pulled that really got to the players.
First what worked on me. Back in the old Ravenloft adventure, The House on Gryphon Hill, way at the beginning of the module we suddenly found ourselves face to face with Count Strahd. In case you don't know he's the villain, an ancient vampire and necromancer. Anyway we fight. Our party consisted of a paladin, a cavalier, a knight of the rose, a cleric/wizard, a thief/ninja type and myself, a druid/ranger. Anyway the 3 tin-cans charge, Strahd turns the stone floor to mud and dispels it when they all fall in. While they're trapped he disentegrates the cleric/wizard, then he cast wall of fire over the trapped fighters. While they're trapped and roasting the thief tries a backstab. He hits and gleefully rolls up mega-damage only to be informed by the DM that Strahd had cast Random Casualty on his dagger (this spell causes the attacker or one of his companions to take the damage from his attacks), so all the damage he just rolled affects him not Strahd. So the ninja just killed himself leaving just me. I nock one of my special wooden arrows. I roll, get a natural twenty and yell "Ha, staked him, he's dust!" To which the DM replies "Strahd looks up from the arrow buried in his chest and smiles evilly at you. Suddenly you all wake up in your room at the inn. It was just a dream. Or was it?" So now we're all scared to death. Strahd wiped the floor with us in just five rounds and now he knows I'm the only one that is a threat to him. Immediately the whole party shifts into high paranoia.
And if that weren't enough through the next three nights the DM somehow catches each of our characters alone. Each time he passes us the same note, "While you are seperated from the party a man steps from the shadows and calls you by name. When you look at him, he seems familiar. Something about his eyes... roll a saving throw behind my screen so you can't see the result." Every time the character rolls he grins wickedly and just continues with the adventure. Someone, for all we know every one of us, is charmed. But we won't know for sure till later. In the mean time, in character each of us knows that each of us has been seperated from the party at one point. So now we know we can't really trust each other. Notch the paranoia up another couple of degrees. And the DM didn't have to do anything else to feed all this. We spent the rest of the game jumping at shadows and making sure our backs weren't too each other.
Now for what I did to my players. It was a Star Wars game, the old West End Games version. My players were in a space battle and just blasting my tiefighters out of the sky one after the other. And this was the third space fight that had gone this way. The other two were escape battles so no big deal, but this one was the one that was supposed to make them crash land where the adventure was going to take place. So they had to lose, but I didn't want to fudge the rolls too bad. So I decided to give one of the tie-pilots the same advantages the characters had, namely character and force points. So suddenly I get to say to the players, "He dodges all three of your shots and shoots at you twice. Roll to dodge." And there all - what, i missed, he hit us, what! Two rounds later, this one tie-fighter is untouched and they are finding a sight for a crash landing. One of them thinks to monitor the imperial frequencies and hears this "Sarigar to Base, the rebels are down. Transmitting last known coordinates now." So know they know they've got more bad guys to worry about and my snap-decision worthy adversary has a name- Sarigar! When we took our first break for the night, he was all the players could talk about. They're wondering how he did that and accusing me of blatant cheating. (even though dice fudging was in the game masters handbook for the old SW game) So I say - What you're the only people in the galaxy with force points! So now they've got all sorts of speculation about how this Sarigar has force points and is he some kind of dark jedi and how do they get rid of him. All this from a snap decision just to get the adventure started. So I can't pass this up, I start taking their own ideas and building this Sarigar into a recurring villain. Eventually the conflict with Sarigar caused two characters to go to the dark side- one roleplayed thru returning to the light and the other (the groups only real jedi) turned in the final battle with Sarigar that killed them both.
So anyway, all this can be pared down to 3 techniques...
1 - use a dream sequence, or some mechanism, to get the players to reveal they're abilities to the bad guy. And make sure the players know that he knows. Then watch them squirm as they try to figure out something new they can pull.
2 - make them think there's a traitor in their midst. This could even tie into the first one. Maybe a henchman switched sides and told the villain everything he knows. The important thing is, now they can't trust anybody. And if you use the tactic that our DM used, they can't even trust themselves.
3 - give the villain the same advantages the players have and play him as though he were a PC as opposed to an NPC. Its important not to get carried away with this. Above all, don't cheat and don't allow the villain to use info that he couldn't have legitimately gained. But other than that, when it comes to a good uber-villain, play him like its you vs. the PC's. Your villain is out to get them, so you should be too. Play it fair and don't make it personal but BE the villain.
