So far we've talked about combat and monsters being as hard as the story calls for, the true power of god, and giving tastes of that power to the players, but now it's time to give that kind of power to the villains. Thugs looking to rob a hero in a back ally is one thing, but truly devious enemies are much more than just stats and abilities. The really memorable villains plot and plan and scheme to get what they want and those are the kinds of guys we're talking about today.
Maybe early on in a campaign villains can get cocky not thinking much of these would be heroes, but as they grow in reputation so should any villains caution about alerting characters like them to what they are up to. In fact I actually prefer to give a couple cocky would be villains to go against would be heroes. It actually covers two bases for you as a GM. First it gives your players a false sense of security to think that villains will be obvious throwing them off guard when they aren't and second it let's you ease players into more and more complex of adversaries.
From the Shadows
By the time your players have made a name for themselves are problem solvers then letting a villain show his hand should be the last thing either you or your villain wants and coming face to face should be out of the question if they can help it. Real masterminds rarely get their own hands dirty. They hire goons, muscle, and and sneaks to do the actual work for them. Now just hiring guys to do your dirty work is one level of protection, but as villains become more complex they also tend to levels on their levels. By the time your players are well versed in the art of heroics they might find themselves faces a villain who is actually manipulating a lesser villain (sometimes without the lesser one even knowing) to hire group or gang leaders that will hire thugs, muscles, and sneaks. As many people that a smart villain can get between himself and those at the bottom doing the more dangerous work the better.
Plans Within Plans
Now that your mastermind has a complex network underneath him its time to figure out who can know what. What separates a mastermind from just a regular villain that happens to have a lot of goons is how he manages them. Plotters and schemers know better than to let others know the entire plan. Perhaps you're dealing with an evil priest looking to raise a demon lord. He might trick a greedy sorcerer into thinking they need certain items to gain ultimate power (usually by placing "convenient" information in their path to discover on their own). Then that sorcerer not wanting to let people know what he's up to might hire a different gang to obtain each item not letting them know about the others and probably even lie as to why he wants each item. A really clever one will even either use fake names or hire a group of people to each hire the gang as to multiple thefts don't all trace back to him. With this the heroes might be stopping several plots that all turn out to be connected, but only if they dig are think to loo into how they might be connected.
Abusers of Power
One big fact a lot of players tend to forget is that NPCs can lie. Sure if you make it obvious that they are talking to a shady or evil character they tend to be more cautious, but the truly devious characters know how to hide those facts from the world. These blinders get even worse if they are hired by the NPC to do something that sounds heroic. This gets EVEN WORSE if that NPC happens to have helped the heroes in the past. Masterminds are completely fine with helping heroes if it serves their needs. If it doesn't help them directly, but also doesn't harm any of their plans then they might see it as an investment. Going back to our example about the priest and the sorcerer if notice the plan ends with the sorcerer thinking they are gaining power and instead summoning the demon for the priest, but what if the priest wants or even needs to be the one to do it? Now he has a potential rival with all his fun toys. That is until he alerts the heroes as to what's going on connecting the dots for them and asks them to defeat the sorcerer and bring these unholy idols to him to be destroyed (because of course he would tell them that's the only way to do it). A truly forward thinking villain would also have slipped themselves into the hero's lives by healing them after a really nasty fight or two (possibly set up by the priest just to be able to patch up the heroes and gain their trust). Now he has the heroes taking out a possible rival while collecting everything he needs.
Not Always a Lie
So I'm sure some of your out there were shaking your heads about "Sense Motive" rolls or any other mechanic your game might have to spot liars. Well first you have to be suspicious enough to look for the lie. I don't care how trained your character is at spotting lies everyone has the ability to believe what they want to. Secondly if the priest tells them that "if the idols fall into the wrong hands a great demon will be summoned and you as protectors of good have a duty to stop this" he isn't lying. Masterminds never fully lie. They warp and twist the truth to their needs. At the worst they tell half truths leaving the heroes to figure what half is the truth. The other thing is they tend to also alwayus believe fully what they say. Truth is a funny thing. IF someone completely believes soemthing to be true it isn't a lie to say it.
A Final Note
This is more of a side note because every villain and really just about any threat should have this. For the love of god give your villains motivation. Know why they are doing what they are doing. Why does this sorcerer want more power and no just because it's power isn't a reason. Think about what makes a character tick. If you plan on a villain lasting more than a session then they are basically another character that deserves the same depth as any player character. Also villains aren't single minded unless their a rampaging beast. If the heroes mess up part of their plan let them adapt. To a mastermind this is just one big game of chess and they always want to be three moves ahead and as a GM you need to be too.