Some clever occlusion code cured the combinatorial explosion. Essentially, there are three passes. First, we clip all objects that are behind the camera. Next, we clip all objects that are offscreen. Finally, we go through all the objects that are fully or partially onscreen, and figure out if any of them completely hide any of the others; if so, we clip the occluded objects as well. (This is likely to happen frequently, since you'd often be flying close to a plent and it would hide half the sky.) Only then have we built the final, and usually much smaller, list of planets to raytrace against.
But that's not all! Since we've gone to all this trouble to figure out the planets' location and radius onscreen, we can then use that as a first pass to reject planets: if the X and Y coordinates of the pixel currently being drawn don't fall within that radius (an extremely fast computation) we don't have to bother with the more expensive 3D intersection test.
So that all worked out just fine, we only do the actual 3-D intersection tests we need, and the framerate is now pleasantly high even when rendering a solar system with fifteen planets in view. Since I'm not expecting to raytrace complex polygonal objects, and even fifteen planets close enough to show discs at once is pretty extreme, this may suit me just fine as a long-term solution... at least, I'm pretty sure the slowest part of the engine is now elsewhere.
Although I kind of hope this delightful success with my home programming project isn't causing some sort of karmic reflection with my work programming project, where I've been stuck on an obscure error deep inside our physics middleware for a few days now. Urgh.