I think one of my favourite NPC names was from the old AD&D trading cards, namely Noj the Double-Edged, a wizard from Spelljammer who had been cursed by his mentor with the phrase "My thy life be forever double-edged". As it was nothing worked right for him, except things that normally didn't work right for others (namely cursed items). Man did my players at University hate him. He wasn't an adversary or anything, but they grew nervous just knowing that he was in the same town as them because the extraordinary bad luck that followed him around.
Another favourite from AD&D is the villain Heironomous Spune from the Bathtime for the Hopping Prophet adventure card in the old city of Greyhawk box set. A priest of Wastri, my players despised this guy as he twice (or it might have been 3 times) managed to attack them, cause no end of a ruckuss and escape with his scaly hide intact. Plus he has a truly awesome name!
The MUD I used to build had an evil dwarf spy chief named Semaj Dnob.
A barbarian in the LARP my brother used to play in was called Dangly Bits.
My recently completed D&D campaign had a PC named Jebodiah of the Many Deaths. A dwarven frenzied berserker that the party kept bringing back to life whenever he perished in battle (which was pretty often). The adventuring group were (and still are) known as The Party With No Name, because they could never agree on one to call themselves. They have also been mockingly referred to as The Party Too Lazy/Stupid To Come Up With A Name by some of their opponents.
