I worry that often times NPC names don't get the treatment they deserve. This can happen for a number of reasons; maybe you didn't expect the players to make a hardware store run, or didn't expect them to become buddies with the cashier. However it happens, when we have the time to name an NPC in advance we should acknowledge how important a thing a name is to creating memorable people.
Let's take a minute and look at one of the greatest fictional names of all time: Keyser Söze. If you haven't seen The Usual Suspects, you are missing out and I'll try not to spoil anything for you.
What makes this name so great? Two main things: it's unique and it has a purpose. If I name a character Mike, I now have the task of overcoming your previous Mike-associations from your entire life. My fictional Mike has to outshine your real life experience with other Mikes to become truly memorable. Does this mean we should never name a character Mike? Of course not, our games are full of people who have no business out shining that Mike you knew in high school. The villain of our story, however, had better stand alone. He must be a Keyser Söze. Never once mentioned in the movie as just Keyser. He is always Keyser Söze. One word, Keyser Söze. Once I think someone says Mr. Söze, but that just makes us here a whisper in our minds reminding us of the full word: Keyser Söze.
The Usual Suspects is a unique whodunit of sorts. The whole movie you just want to know who the infamous Keyser Söze is. This is a name that defies immediate association with a specific ethnicity, it's not Mr. Chang. Literally anyone in the movie could be the Keyser Söze. The sound of the name functions to further cloud our ability to determine who he really is.
Does this mean we should never have a major character with a completely ordinary name? Of course not. But it does mean that we as GMs have to try that much harder to fill that giant (full of associations) name with character instead of having the name predicate the character.
When it's reasonable I try and make the most unique characters have the most unique names. Remember, unique doesn't mean ridiculous, and it doesn't mean absurd. My current campaign has a paranoid ex-mercenary who owns a junk yard. He is probably the most bizarre character in that games world, and as such, his name is FreeBid. The only rule is (and every character has told the PCs this for a long time before they ever met him) You NEVER ask him why his name is FreeBid. Of course they obsessively want to know, and they have to find out before the campaign ends. There isn't room for a handful of characters like FreeBid in a believable world, though; that makes him special.
A disgusting slob that gave missions to the players in a campaign I once ran had the name Landry. He was the only Landry they knew, and I always began their interactions with him by describing the most interesting stains on his clothing. Landry apparently never does laundry. I'm not sure if the players have even made this connection (they tend to have a lot on their minds), but "Landry" has become synonymous with disgusting in the world of that game.
When a character just has to have a dime a dozen name, I make sure that they are defined by their location, job, catchphrase, or all of the above. Another time I charged my players with finding a rube that could be propped up as a puppet mayor. They decided on an old man named Ol' Hank. Hank's a common name, but every time they encountered him, they found him sitting on a porch, patio, veranda, deck, etc. having a charming conversation with a woman half his age. Hank became a character they remembered because of all the ways his location would manifest itself. There was a pawn shop owner with a rather common name also that I wanted the players to latch on to, since he would become important later. He had a catch phrase where every time it was natural in conversation he would remind them he had run this store "same location, 27 years." The players eventually started to say it in connection with, or sometimes in place of, his name in conversation.
A normal name can stand out for just being normal. Let's talk about Norman Bates. What's more normal than Norman? And seriously, a peeping-tom with the last name Bates? It's perfect. It's an unassuming name that works in perfect contrast with what he is, a psycho. Names don't always have to describe the person, sometimes they work best when they don't. Name a giant biker Shel, short for Shelly. They will remember that. Note: I didn't say to name the biker Cupcake. There might be a time and place for that, but Shelly could just be an unfortunate parental mistake - Cupcake is not.
Two other magical names I just have to mention; names that became part of our cultural heritage just like Norman Bates: Hannibal Lecter and Buffalo Bill.
Hannibal Lecter is such an evocative name. It is a unique sound, but the rhyme with cannibal (before you even knew he was one) combined with the historical reference was amazing. Combining that with Lecter, a word that autocorrect wants to replace with Lecture or Lectern - a method for disseminating knowledge and an object which speakers stand behind. This, for a character who talks condescendingly at length about his own intelligence. You place this opposite a character they call Buffalo Bill, a wild name that conjures the opposite types of ideas than the intelligence of Hannibal Lecter and the characterization is palpable. .
Names are so important in fiction, and we should do them the same level of justice for our own creations.