At the moment, everything is still brute force checking against the map polygons, but only checking against each other if they are in the same or adjacent zones on the map.
I've also stopped trying to render anything that is off screen. Direct3D's clipping seems hard to beat manually, but by doing a simple vector-vector distance check before calling the rendering routine, I save doing all the manual transformation and rotation. Don't tell anyone I'm doing this manually though, as they'll probably shout at me.
With all the new optimisations in place, I had a thousand planets spread over an 8000x8000 pixel area all colliding with the map, the ship and each other with no drop in framerate. Win!
Obviously if they are more densely clustered, the framerate suffers, but I don't really see a solution to that. Since the game is doing frame-rate-independant movement, the worse that can happen is that the animation goes a bit choppy.
Might look into using the Direct3D transformations rather than my own (using sinf(), cosf() et al) to see if they are any quicker. I guess they probably are since I assume they are done on the graphics card.