they are on the map, but i really liked the suggestion made last night in chat that they be searchable in the new map search interface. a layer would be created upon searching for a particular shrine or vendor that highlights streets with what you're looking for, or dims out the streets that don't.
also, i actually would prefer to not have the unvisited streets available to view on the map automatically, as it would shift the dynamic of visiting new streets from stumbling onto a previously unvisited street into an exciting suprise, to a grindy chore of visiting all the streets. it would be nice, however, if we could have the option to mark our own notes, as has been previously noted, so people could choose to do this themselves. perhaps advanced cartography skills could allow such a thing?
+1 on layers and I'd also like shrines & vendors to be searchable. I also like katlazam's suggestion of being able to turn off seeing unvisited streets and adding notes. Perhaps the notes could have an option to be shared with anybody in a group or in your friends list. That way you could have a map of best mining spots, a map of best places to find certain trees, etc...