My all-time most memorable NPC: Mordecai the Evil Flamboyant Dwarf. He was the main villain in a D&D 3E campaign. He stole the macguffin from the PCs, and they spent the next several game sessions trying to get it back. He was sort of a classic "dashing" bad guy - he dressed real fancy, and was unfailingly charming and polite.
Why he was awesome: Often in my D&D games, the Big Bad Guy was intimidating solely because of his stat block. Mordecai was genuinely frightening as a character, to the point that the PCs fled town when they realized he was there and *might* be after them. As someone responsible for making the game fun, that was an enormously gratifying moment. They were all like "Oh shit, no way. We're getting OUT OF HERE."
And there was never a single combat scene with him!
How I made him awesome: In the first session with this NPC, I presented him as color, instead of a threat. The PCs liked him, and assumed he was in the adventure as a source of information. Then, after he robbed them, and they went after him, they decided he was merely a low-level distraction.
But in later sessions, they met other people who were fearful of him or warned them about him - slamming doors at the sound of his name, or lowlifes fearfully claiming to know nothing of him while looking over their shoulder, that sort of thing.
Then there was a big "storm the tower!" session where they went up against a sorceress and her various dungeon-style minions (iron golems!), only to find that Mordecai had beaten them there, and assassinated the sorceress in a gruesome and horrible fashion. Since *she* was a known bad-ass, they inferred all kinds of stuff about *his* capabilities without me having to drop broad hints.
So I tried hard to always show the effect he had on the world as a bad guy, rather than telling them he was a major villain, or just having him kick their asses in a fight.
I don't do that often enough.