That said, on further reflection I'm not sure what the micro-pulses do for you. Option 3 already gets you, with a little math, the time and location of the explosion. Just make an ordered list of possible explosions, march down, and take out destroyed missiles as necessary.
Steve may or may not get benefit from the micro-pulses depending on how things are working underneath the hood. If all of the accelerations or velocities of ships and missiles stay constant during a sub-pulse, than he probably could just use a Hermite Interpolation method and in order to find the positions and velocities of all of the bodies involved just as accurately as if he was propagating them with micro-pulses.
However if he is using those micro-pulses to allow the ships and especially missiles to update their accelerations on a much finer scale each time step, then there really isn't any way to replicate that via interpolation.
For reference, a Hermite Interpolation algorithm can be written from the following two wikipedia pages:
http://en.wikipedia.org/wiki/Hermite_interpolationhttp://en.wikipedia.org/wiki/Divided_differencesThis problem sounds fundamentally similar to a common problem with 3D physics engines. I'm not familiar with how it's handled, but the problem may already have been resolved (or at least mitigated) there in a way you can reuse.
It is similar to the problem of collision detection in other environments, yes. The easiest example is with buildings and walls, if collision was only detected on each simulation time-step then for any non-infinitesimal timescale there would be a chance of bullets passing through walls by being just before the wall on one step and just after the wall on the next step. The way you get around this is by doing collision detection not on the point of the bullet, but on a cylinder that goes from the bullets last position, to it's new position, and is the width of the bullet.
That is a much similar problem though, because you are interested in the collision with static walls or (relatively) slow moving models. Here the problem is more similar to trying to track whether one bullet hit another bullet, you now need to track the motion of both objects.
Not only that, but depending on the accelerations involved you can't even assume that the ships and missiles are moving in straight lines anymore, which entails slightly more time-consuming calculations for the computer to figure out whether they hit. In fact, that may be reason enough for the micro-pulses right there, so that the time scales get small enough that it's accurate to assume that each ship is travelling on a straight line for each sub-pulse. That would let you use the constant time "Where is the closest intersection point between these two lines and how far apart are they then" operation on the lines, instead of... Probably the Newton's root finder method with the time as the input and the distance between the two bodies as the output.