While it's true that we'll never run out of unexplored stars, the number of nebula in the galaxy map is limited, and I'm pretty sure that all the interesting destinations within a few 1000ly have been explored already. There will still be plenty stars left in a system like Orion where there is a ton of stars on top of each other, yet you can be sure that all the big ones have been tagged already. Too bad you don't know if it's already explored until you get there.
It ruined Mirrormoon EP for me. It was worse there though, each planet was a little puzzle to be solved. Everything was solved already when I got to the game.
.
Anyway yeah, seeing graffiti everywhere weakens immersion a bit. I wonder what Columbus would have thought if he found signs everywhere, explored by Leif Erikson