Every villain doesn't have to be like Sun Yu. It would be difficult if the PCs had to face someone who planned years ahead for every possible scenario and prepared counter moves for all conceivable methods of attack. But once in a while, it isn't such a bad thing to throw a patient and skilled strategist their way.
The exact shape of your villain's schemes will be dependent on the details of the campaign, but there are some basic things you can keep in mind.
Play Him Like PC (But Not a GMPC)
Player Characters can be smart. They don't just storm a palace swords drawn and charging; if their clever they come up with a plan to take the villain off guard. Certainly some PCs do rush in and hack at everything that moves, but many of them hedge their bets and do what they can to ensure their ultimate victory. A smart villain who inhabits the same world as the PCs would be able to plan in this way as well. He can take all the same 10-foot pole measures a party of player characters do.
The big difference I find between a PC and NPC, is the time investment. Most NPCs don't get the planning and prep that a PC does. The demands of the game require that you quickly assign their spells and abilities. Players have the luxury of deliberating and focusing for the one character, whereas the GM has many characters to manage. So you need to devote a little more time than normal to the truly cunning NPC. You don't need to veer into GMPC territory here. He can still fail. He just gets more of a fair shot than most non-player characters.
Advance Preparations Shouldn't be Done on the Fly
If your villain has some secret means of escape or has planted a spy in the party, be sure to flesh out those details prior to play and not midstream. Don't turn Orik the Henchmen into a spy six games in, plant him there from the very start with the intention of being your villain's inside guy (and allow him to be discovered if the players are diligent enough before the big reveal). Players are good at spotting the difference between a sudden invention on the fly and something that was planned ahead of time. Your villain will seem smarter if you actually prepare a strategy in advance.
Play it over the Long Haul and Tie it Together
The villains plan doesn't need to be introduced and culminate in one or two sessions. You can stagger it in bits and pieces over the long term. Little pieces that seem unrelated here and there can be introduced, perhaps before the players even know they are up against a major threat. This allows it to be tied together convincingly later on. When the players look back and realize that the four artifacts they thought they discovered through sheer their own efforts and good luck were a product of someone else's machinations, that can be really powerful. The important thing is not to railroad. Your villain's plan should rise or fall on its own merits, so you want to put plenty of effort into making all these pieces work in a way that doesn't expose the ploy too early but makes legitimate sense in hindsight.
An intelligent and strategic villain anticipates the actions of his enemies and knows how to turn them in his favor. He isn't just going to play it by ear when the big showdown happens, he's going to plan and research his opponent. He will learn that they often open every fight with Esmerelda's Bolt of Anguish and take steps to turn that against them. Again these things shouldn't be devised on the fly but prep made in advance.
One important detail here is the your villain needs some way of obtaining this information. Don't simply assume he knows everything you do. Identify the people he can learn this information from and determine if he has access to them. For example he may interview those who faced the PCs and survived. Or he may send some of his own men in disguise to feel them out.
An Intelligent and Wicked Villain may not be Constrained by Righteousness
Player Characters, even evil PCs, are usually constrained by the fact that they basically played by people who are not villains. You need to be much worse than them. Your bad guys can revel in their wickedness if they're inclined. Their schemes are not just impressive, they are horrifying. In Killer Clans, part of Sun Yu's contingency involves a family planted in a specific area with the goal of helping him escape and hiding. However he knows that anyone who finds the family will soon learn his whereabouts by using torture or other coercive means. So he exploits the father and mother's sense of loyalty to him and to the Lung Men Society. Not only do they voluntarily kill themselves to protect Sun Yu, they give their two children a fatal dose of poison. This is one of the most horrifying scenes in the film and when you realize how determined Sun Yu is to survive, no matter who hast to die in the process. Imagine a villain in your campaign with this kind of determination. So feel free to slaughter the innocent if it serves the strategic aims of your villain.
When your prepping for a game it is easy to go on autopilot. Avoid this by putting the notepad or keyboard aside, leaning back and just thinking things through from the villain's point of view. Think about what he wants and what resources are at his disposal to obtain that. You don't need to be a genius to play one in a game, but you do have to convince the players that they are facing a genuine mental talent. I'm certainly no genius. With enough time and thought you can fake it. Treat it as a thought experiment. Think of the things you've really wanted in life and how much thought and effort went into getting them. Your villain is doing the same thing. The stakes for him are enormously high and he isn't just going to wing his grand plan, he's going to think day and night about his goals. This ties back to the first point of playing him like a PC, in the sense that you need to commit the time investment in the character.