EDIT: Hey you're right, if I draw the planets and skybox first and then clear the z buffer, I should get exactly the output I want. I guess the only complaint would be that often the skybox takes up very little of the screen, and is therefore usually drawn last.
You're worried about the performance of drawing the full skybox, when usually it would be mostly blocked by objects in front? I'm hardly an expert on graphics performance but I wouldn't think it would be a big deal.
If you're really worried, you could experiment by drawing the skybox a bunch of times per frame and see how many you can do before it affects frame rate. If the answer is in the single digits, maybe worry about it... if in the hundreds, safe to ignore. That would be easy enough to do, and should quickly assuage your fears without doing serious profiling or anything.