Not only do I agree that landmarks should be notated, I think they should be heavily emphasized so that the map will have more purpose. I think it's surely about time for some new ones to be forged into the current map in order to make some dull places seem more interesting to adventure towards.
Meaning: If players have a map of all sorts of interesting things in any direction, they will see that and the game will instantly be a good bit more interesting. Right now I check out the map and see nothing worth traveling to.