Well, under the mini map they have coordinates, so we could put those for the NPC's location, though that could be confusing too. Maybe just put links to the NPC's page and have more info on them there? Then we could do both map and coordinates, as well as an NPC image.
Baa baa black sheep have you any booze? No sir, no sir, I'm a....sheep~