Sometimes one of my ships spots a starbase because it is nearby, and when it leaves it vanishes from the map. 

Since starbases do not move, and their location are an important strategic importance, I would expect any ship spotting a starbase to record its location so that my civilization can make use of this information.  It does not make sense for a starbase to go back to being hidden after it has been spotted by one of my ships.

If that starbase is destroyed, it should still be displayed on my map unless one of my ship/starbase goes within sensor range of where it was and updates the map again for me.