I think advice to have a villain with strong, believable motivations is good. So is advice for an interesting backstory. The thing is, this is good advice for any NPC.
I consider a villain especially successful when the players have a deep hatred of the guy. It can't be the kind of hatred where they never want to hear his name or have him show up in the game. That's a sign that I've failed. Instead, they need to assume he's behind every bad thing that happens. They need to talk about him when he didn't show up this game, and think about what they'll do when they catch him, and they need to take their plans for how to off him much too seriously.
So, how do you inspire that? I think Eric Weilnau was right on: you have him beat them. If he shows up just every once in a while to foil their plans at the last minute, after everything else seems like it was on rails, they will hate him passionately. It can't just be a deux ex machina defeat: it should be done with style, so that they have to at least admit that they got beaten. I like to hear the players laugh at how thoroughly they got beaten, and then swear a blue streak about the guy who did it. Also, the more face time they get with the villain or his minions, the better. "You could kill him, except it would not work out for you in the end" scenes are good for this. I like to imagine villains as "the guy with whom you have a sporting competition, except that you really really want to murder him." This is Ben Linus from Lost, or that jerk who steals your chest in Zork 3.
There's another category of big bad guy, though, who I wouldn't call a villain. I'm not sure what I would call him. How about "the alpha monster?" This is the big evil horrible thing that's performing horrible deeps just out of reach, and clearly has to be stopped -- or just survived -- by the PCs. You never want direct face time with this guy, because he will TPK you unless you absolutely know just what you're doing. He doesn't foil the PCs' plans, because he doesn't "foil plans." He is an 800 pound gorilla. This is the smoke monster from Lost, or the thief from Zork 1.
Building this guy up isn't too hard, either: you spread rumors at first, then let the PCs get a glimpse of the kind of destruction the alpha monster wreaks. Then maybe a few close encounters where the PCs feel like they're in a lot of danger (whether or not they are). Eventually, a climactic battle. I'd probably recommend against more than one battle with the alpha monster. Either he gets killed or he commits TPK. That's just how he rolls.
If it turns out that the alpha monster is the fault of the villain? Hey that's just gravy.