My personal opinion is that they need to add parchment into the game, since it is made from animal skins, take away the mini map feature, and add cartography into the mix. OR just let people make their own maps using a symbol stamping system on the parchment. Then players might actually have to learn how to find their way around without the magic locator beacon.
Want to know where you are? Pull out the actual map and look for landmarks and make an 'educated' guess. Want to make a note or mark? Write it on the map you own.
Not likely, but totally doable.