The only thing I would add about the labels is to keep them limited to only those that are needed for the story. If nothing happens in Village A as the characters pass through, for instance, it probably doesn't need a label. Also, you might the Belgariad Omnibus (by David Eddings), the Cleric Quintet (by R. A. Salvatore) or maybe some of Dennis McKiernan's Mythgar books for good examples of what you are trying to achieve.