Before I dive in, I just wanted to say that these things are by no mean exclusive or that they are the perfect solutions. They are, still, things that worked for me.
Make them resourceful
Giving your villain resources is one of the best ways to make her powerful. These resources don't have to be money, as power, intellect or technology can serve this purpose also. But so can manpower, for example, as can many many more. Your villain should be different from ordinary enemies, but in order to show that she has to survive somehow. Resources are one of the best ways to make sure of that.
Make them well-rounded
Villains aren't just bad. There is something more to them, something that makes them more than cardstock figures. This thing is the depths of their character. They are deep characters, with goals and rules and the like. They have internal conflicts just like the PCs. Look for example on Dr. Horrible. He's a villain, but he has rules which create a kind of paradox within his character: He won't kill anybody; he won't fight near children 'cause he doesn't want to hurt them and so on. Look on Vito Corleone, who holds enough power to rule Manhattan but who won't do that because he wants to keep his family safe, because he doesn't want his youngest son to be a mobster like him. Those characters are deep, and because of that we keep them in our hearts. If your players can't see the villains as real persons, they won't care for them.
Make their threats personal
Villains carry power, true, but it is the knowledge about how to use it and where and when to use it that makes them so frightening. Look for example on The Joker in the movie The Dark Knights: He forces Batman to choose between the person he loves and the person who represent the future of Gotham City. There is a reason that most villains attack the persons closest to the heroes: It makes the heroes less carful and far less logical. It makes the heroes frightened. It is one of the most common reasons that Superheroes have a secret identity. Make the villain attack the core beliefs of the PCs and they'll care for them like no others.
Make them colorful
Your villains should be cool and full of colors and surprises. The Joker is again a good example here, with his insanity and his contempt to everything that society is expecting from him. Look at Buffy's Big Bads, each of them is so unique that you can't forget them, with their witty remarks and special ways of targeting Buffy and her friends.
Make them close to the characters
Remember season six of Buffy, with Willow being the Big Bad? This is the single most frightening and strong villain Buffy has ever created. She comes from within the Scooby Gang; she was there from the very start. She is still Willow, so they can't just kill her, but she's not Willow entirely. This is another great way to target those closest to the Pcs, making their enemies come from those closest to them, those who know all of their secrets, and those who they have counted on.
Make them somehow dependent on the PCs
This is a little bit trickier, but when done right can create some truly villainous villains. The villain is dependent on the PCs for her success. The PCs actions help the villain somehow. This creates a sense of personal horror that attributes to a greater fear of the villain. Much more thought is bestowed on a villain who advances from your own advances. Much more energy is spent to stop her than if she's static or completely free to advance on her own.
Make the PCs somehow dependent on the villain
The last section is extremely amazing when combined with this one, although again this is good on its own. In order to defeat other villains, to stop other menaces and threats, the PCs need the help of the villain. Think about Rumple from Once Upon a Time: He's a complete villain but everyone needs his help in order to achieve their goals so they can't just kill him. Furthermore, he is getting stronger from each bargain that they make with him, so he becomes even more frightening.
Analyze villains that you like
Last but not least, try to analyze the villains that you like most when watching them in action. Try to find what makes you love to hate them so much. Some of the tricks you'll find in the list above, while many a time you will find things that are completely unique to those villains. Try to incorporate those too to your villains.
