It's impossible to calculate all the positions of all the planets/moons/etc every second (as far as i know) so it seems that I'm at an impasse with what to do as far as the planets (at least not on my PC I can only calc up to around 20,000 orbits at once without noticeable bad slow down)
Make objects relative to one another and layer your architecture.
What I did was base my map around the position of stars. All planets orbiting a star only have a position that is relative to that star so its easier to update. And all moons have a position that is relative to their parent planet.
Makes it much easier, and you can enable/disable updating star children if there is no current visibility (do keep a counter to keep track of time so that when you update everything is in sync).
Note: Plotting intercept course for ships might be a bitch when you have to factor movement however. The ETA will not be accurate unless you factor the expected movement of the planet.