Interesting. I'm doing a space game myself and I have been wondering about this problem also. Gonna try that StarDust thingy.
Other idea I had was multiple skyboxes...layered. So you have far-distant stars, not-so-far stars and stars that are close. (or more layers). It might give some depth, but I haven't figured out how to make the skyboxes transparent so they don't hide the skybox in behind.
I was also thinking about particle effects... but, hm, there are many many stars
needless to say, I think it's a overkill to have each star as a white triangle or something.
Also, I was thinking about animation.... stars do "blink"... doable with particle effects.... but also with a skybox that gets alternated.