Many interesting ideas in this thread, some directly contradicting my experience, so it's obviously group-dependant.
1. Attacking the thing the PCs (and players, in fact) are invested in
Burning their stronghold, taking their stuff, killing the NPCs they are attached to... I can see that working, but I also found that it tend to have players invest themselves less in the world. "What's the point in building a stronghold if it will be razed by the next dragon?" "What's the point of getting attached to NPC X if he'll be kidnapped... several times? Let's not let the GM have leverage on us, henceforth we will be loners, going from tavern to tavern and we'll never have more than a business relationship with anyone not having the PC glow around him". Being to "heavy-handed" can make this approach backfire in the long run. I have found that having the villain just... ignore them or consider them beneath him. Not being respected as heroes is something that infuriates PCs even when they're with allies, let alone foes. PC Sherlock Holmes would immediately hate Moriarty if Moriarty was saying "Him? Let him go. Sherlock is no threat, the real threat is Lestrade, not his incompetent henchman!" Lack of respect is a strong motivator.
2. Taking their stuff...
Sure, PCs tend to have an extended notion of property rights. You took my stuff, I'll cross the world over to kill you, even if I actually got my stuff back 18 sessions ago... But it borders on another problem... the KoS problem. You absolutely need to telegraph that the big boss is above their ability to defeat when they meet him. If not, you risk them to fight to the death instead of letting themselves become prisonners & being captured. There is some sense that the GM is expected to provide CR-appropriate foes for the players. The idea (present in real life and MMORPG) that some monsters are very dangerous and can kill you easily is less present in D&D. As the system also allows large power discrepancy, half of the PCs can be dead before they realize... and even then, they might not accept defeat as a solution. Risking a TPK and campaign failure because one wanted to make the players invested with the villain is not a success. Players are prone to do reckless things.
3. Have the villain be an organization, not a single foe
This is my favorite trick. It makes confrontation possible. If X the villain is killed during session 2, before establishing his backstory, then the real leader was Y, not X. Once they have started hating the faction and his leader by extension, then it's time to let them get clues about the villain (and avoid any direct confrontation, except in a context where it's not possible to use violence (meeting in public place like the king's court). Not all villain need to be KoS by everyone, if your villain is a noble family wanting to overthrow the king, they are the king cousins before proof can be delivered and so they can basically go wherever they want and the PCs would be unwise to harass them. Il also prevent scry-and-die techniques until they discover the identity of the true leader of the organization they are fighting.
4. Make sure you give the PCs the time to get information about the villain but don't force it down their throats. There is no saddest story that the GREAT backsory of your villain the PCs didn't get the opportunity to discover because the campaign went in another direction. But there is a risk that the GM becomes too invested into his villain's story to allow the PCs to bypass/ignore it completely. It's first and foremost the PCs story, and explaining the villain backstory must be organic to the story of the PCS.
5. Make the villain plan realistic and not evil overlord-like (or have him read the list)
Single foes are easily defeated. If you want your villain to have some staying power, he must confront the heroes and escape (thanks to his henchman dying for him to buy him time). Nobody will die for a raving lunatic, even if he pays well. The servant must be convinced they are working for the greater good (ideally) or at least for something neutral. Even the mafia tries to pass as good, and blatantly terrorist organizations can have armies because the rank and file believes that they're right/doing the right thing. Nationalistic conflicts are better for this than "destroy the world" scenarios, religious, too: the villain's army must be sustained by something. Bonus point if the players can see the villain having a good point to act like that and could see themselves in the same situation as him.