Billboards are a nice idea, thanks for the tip.

But I have got another problem: in my game, all textures look like being drawn with only 256 colors, but in fact I have set the color-depth to 16bit. What could I be doing wrong? I checked all my texture-loading-methods and everything is set to good quality.
So what could be wrong?

@SKREAMZ:

Nice pictures, but what is specially about the background in freelancer? The nebulas?

well it makes you feel like you are flying through space. you can fly through nebulas, gas clouds and other things you see.

Those gas clouds and nebulas are not part of the skybox, they are objects in the space. Just like an asteroid or a space station.
I do not know how to draw them (the nebulas), but they are just a part of the scene, not just simply background.

FYI (not sure if this was mentioned): You should disable the depth buffer when drawing your background. A portion of the lag associated with drawing something, especially if it covers the entire scene, is the depth buffer test. The object has to be tested with whatever is in the depth buffer and write in the buffer if it is closer (since the buffer is clear when you draw your background, it will test and write for each pixel on the screen)...you dont need to do this for a background since it should always be drawn over.

Good luck with your game,
- llvllatrix

Octrees and frustrum culling also work well with space sims (space to object ratio ;) ).