I started thinking about memorable names in the context of genre fiction, as I was reading the book The Goblin Emperor by Katherine Addison. I absolutely loved the book, but what hampered my enjoyment at times was the incomprehensible naming of people, places, and things in the fictional universe of the story. For example, the titular Emperor has two sets of servants: the nohecharei, who are like bodyguards, and the edocharei, who are his attendants. There is one character named Tethimar, and another named Telimezh. It was challenging for me, an avid reader of fantasy, to keep everything straight.
It's clear that the author of The Goblin Emperor decided to value authenticity within the fictional vernacular she created over the reader's ease of understanding, and it is not my place to condemn that choice. However, it did get me thinking about what features of fictional names make them more memorable, especially within my discipline of game design, where the narrative has less room for rote repetition. Below are a few ways of keeping your proper nouns lucid.
1. Decide whether it ought to be a proper noun at all. Sometimes the best name is just a description of what the place or thing is. Take a look at this fragment of a map from Metroid Prime to see what I mean. Of 10 named places, only 2 include proper names. The rest are simply descriptive.
2. Use a close variant of an existing name. It may feel a bit like cheating, but re-using the existing circuitry in your player's mind can be very effective, and serve the overall enjoyment of the game. Writers do this all the time with place names like "New Tokyo" or "Earth II." Slight variations work for human (or other sentient being) names as well, such as Snow Crash's "Da5id."
Needless to say, to pull this off, you'll have to have some idea of what your reader considers a 'common name,' so this will be culture-specific and may need to be localized.
3. Accompanying titles. People tend to remember the relationships between people and places better than they remember the names. Think back to the last time someone described the plot of a half-remembered movie. It probably sounded something like "...and then the main guy's best friend went back to their old apartment and got the thing..." No proper names at all, just relationships. We can use this to our advantage by putting the relationship right into the name!
The simplest example is titles like "Professor," "Captain," "Archduke," "Counselor," etc. If you're in a more fantastical setting, you can use things like "King-son" and "Friend Luke" as names, too. Anything you can do to associate the name with a relationship will help, and when you've repeated it enough times you can drop the relationship prefix without confusion.
4. Distinct explicit or implied ethnicity can make each of your names distinct. If you have three main characters -- one an American farm-boy named John, one a burly Norwegian named Jøhan, and one a Chinese national named Jao Han, the player will remember the names distinctly, despite how similarly they are spelled.
5. The Bouba/Kiki Effect is an apparently universal human trait which makes us associate certain qualities of sound with physical characteristics almost synaesthetically. Hard angular things are associated with hard angular sounds, like "knicknack" and "porcupine," whereas softer, rounder things get softer, rounder sounds, like "balloon" and "butterfly." You can use this property of natural language, making your names tacitly descriptive of their subject. If your villain is sharp-nosed and bony, you may want to name him "Jack" instead of "Bob." Likewise, a domed hall might better be "Woterbund" than "Rinkertin."
6. Gendered Suffixes cause many names to be self-descriptive, at least to english-speaking ears. For characters that identify as a certain gender, certain sounds can serve as clues. In vowels, for example, -a, -i, and -y sound more feminine than -o and -u. For example consider "Brandi" vs "Brando." There are exceptions, of course, but I think these indicators still have their place in some fictional worlds.
7. Uncommon letters in proper names should be hoarded like the precious resource they are. Don't use them all up in a single name like "Quizikjax." Doling out one uncommon letter to each character can make each name stand out, but not overshadow any others. The least frequently-used letters in english are Z, Q, X, J, K, and V. However, Even the most-used letter, "E," can seem weird within a name where it's not expected, like "Melodee," so context can make a big difference.
I hope these ideas are at least thought-provoking, and are of use as you create and name people, places and things in games and elsewhere.