There were loops in SC1, so a minimal spanning tree method is definitely not the way.
Which is why I said its main utility would be to ensure we don't get isolated clusters, with loops achieved by other means. MST is not the only way to do this of course, I'm going to mention another later in this post.
As for sensitivity of parameters... I don't see that as a problem.
It becomes a problem if a large fraction of one's parameter space gives undesirable results, such that it's just a narrow band one is aiming for. This was just my first impression, though, maybe the ``undesirables" I was thinking of are actually ``interesting".
Here's a map with the connections drawn in (and that was a tedious task of note)
Thanks for posting those linked stars, they are illuminating!
Hmm, that dead end with two stars near the plus sign is interesting, or maybe not if it's actually not so close in 3D to that other arm of stars.
Nah, really I was being facetious. That's what directX and friends are for 
I really need to branch out beyond my numerical box . . .
At least to generate gameplay interesting maps higher level structures would be needed to create it. eg: LineOfStars could contain stars and the end points of other lines of stars. Unfortunately we're wondering into realms I haven't thought about so I don't have anything valuable to add yet. What I would like to do is keep the clusteryness of Zeracles' stars but I don't think that should be a problem if one generates fractal regions/volumes and then places lines of stars (etc..) within them.
Ah, now this is interesting, fractal. A fractal set of points might be connected by a graph that isn't fractal. An MST should preserve the fractal nature of it but if that's followed up by connecting all points separated by less than some arbitrary distance, the self-similarity is broken.
I thought of a graph that should preserve the self-similarity, called the
Delaunay Tesselation. It's related to the
Voronoi Tesselation and I think it has some nice properties. It makes closed loops on all scales, connects all the points and doesn't do crazy interconnectedness. It also removes any arbitrary choices in the assignment of links, leaving that choice to the structure in the distribution . . . which is where I would choose to put it; there should be a reasonable intuition between the distribution of points and the links in the end result, in my opinion.
The problem with DT is that it doesn't do dead ends - there are way too many triangles to emulate what was in SC1. Looking at the image Dragon posted, perhaps this problem could be solved by removing all links above some arbitrary length (retaining all MST links to ensure all stars remain linked). The user could then choose how much to reduce the interconnectedness - effectively, how many dead ends to substitute for the triangles, without fear of creating isolated clusters. Just another possibility thrown out there.
EDITed many times for clarity.