It would be a nice touch if the stars start out as nameless and only got named after someone settles them and give them a name specific for _their_ race. For example there might be a syllable list (editable of course) for each race and a star system would then be given a name consisting of 2-3 random syllables.
The human list could produce names like "Hub" + "ble", "Lon" + "don", and "Ta" + "too" + "ine" which clearly mean nothing and are only random noise
but are pronouncable enough. Similarly an insectoid race could have systems like "(clack)" + "(chk)" and "(feeeeh)" + "(pk)".
If the RNG gives a duplicate we just assign a "New" in front of it.
I mean there's a definite feel in a game where you can conquer a system named "New (clack)(clack)".
I like this idea. I think it would give the galaxy a bit more flavor. Centuries after an successful campaign against an competing empire, you could still identify the systems you conquered from them by the sound of the planet names.
Each race might have a data file that contained the average length of star names (in syllables), a "first syllable" list, a "last syllable" list, and a series of "middle syllables", + common prefixes and suffixes... for example...
Average length: 3 (+/-1)
Prefix Occurance: 20%
Suffix Occurance: 10%
Of course, these lists are quite short, and the program would have to check existing star names to make sure their were no overlaps. Also, one prefix could be designated as that race's word for "new" and thus might only be applied to existing star names.
Another idea: Whenever a player wins with a particular race, they could add a star name to that race's dictionary (ala "Spaceward Ho!"). Synchronization issues could be avoided in multiplayer games by having the name pulled from the local dictionaries for whichever computer was controlling the race that named a new star.