In the old novel The Wizardry Compiled, residents of the world with magic couldn't make representative maps due to the law of similarity. The map would start to have an effect on the world and vice versa. Their technique for navigation was to use lists of descriptive waypoints rather than to make visual/spatial representations of the area of interest. Of course, there is one point in the book where a map is produced, but it's produced by direct visual feeds and so presumably doesn't have any significant distortion of the world by its mere presence.