well if you arent simulating the entire galaxy rotation and galaxies moving away from each other and stuff, then you could cut corners on more things, because calculating everything sounds like a lot of math.

planet 1 is a position X, planet 2 at B now, depending on the situation you would want to WAIT for your launch because another date will provide an EARLIER arrival, for example, if you go all simulator-ish. Also imagine the planets orbits moving them in a way that the sun (or another planet) is on the way, your ship will go through it.

I assume you have orbits a a mathematical function?, for in-system travel I'd suggest you calculate the distance to travel at launch, set that as a the travel distance no matter what (even if the planets are accelerating away from each other at the time), and update the travel % each tick if you must (you don't need to know the planets current position for this btw, and no you dont need to update the % every tick either).

Then when you need to display the ship on screen, just make a nice spline curve that follows the possible orbit (or counter orbit) between the current position of both planets and set the ship at the correct % of the way, regardless of the actual current distance seen vs traveled, doubt anyone will notice you are off a few light years, or care, even if they do notice. Doing this you could solve the "planet in between" issue by detecting if your ship is inside a planet, and adding an "slingshot" curve around that planet, then draw the ship using it as a slingshot.

Are you sure you need more then 20 000 planets in the game? For what will they all be used?

If they are not an important game mechanics (and i dont see how any player can deal with that amount of objects in a meaningful and fun way) you are just wasting resources imho.

Are you planning some sort of mega eve online? Might be hard to pull of:)

I think I understand your issue. Plotting trajectories including gravity from multiple objects can lead to complex differential equations, especially if you need to skip large amounts of time. Skipping any large chunk of time in physics can lead to different results.

My first question is whether you can have fixed planet orbits, rather than calculating them at run-time. If so, then gravity becomes a one-way thing, e.g. planets emit it, ships are acted on by it. That would ease things considerably.

I'm not sure about 20,000 planets... yikes! For a much smaller number of planets you could fix the time skipping issue by fudging with precalculated values. e.g. for each pair of planets precalculate some trajectories for various points in the orbits, and use those when the player isn't watching.

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.