I like the clustering Idea, where you pick a random, large enough star and create a cluster based on it.
Stars in the border regions could be randomly assigned to one cluster, and thus might have slightly different positions.
I also really like the idea of having a large 2D map and when selecting a star it shows you the select distance around it in 3D.
You could also partially flatten it, like picking a cluster with a radius of, say, 75 LY, and giving it a maximum height of 50, and everything above that would be cut down by 50% Z coordinate or to 50 LY displacement, whatever is less change.
That way, it'd limit it to a reasonable sphere the player can look at.
The reason I suggested that some stars are not reachable (they don't need to be invisible, though toggling would be nice) was that otherwise, basically every game would play the same, the player visits the closest systems first that are large enough to have a good chance for whatever. Whatever's worth your fuel.
Those stars needn't be of limits, just not reachable in the start of the game, maybe require Hyper-Level 3 or just counting as a higher distance for the risk/accuracy.
Where, I suppose that horse's been beaten.^^
