The problem is that nothing can happen "instantaneously", everything needs a certain amount of time, no matter how short. You say that there are supposed to be UFOs that can turn instantly, but if someone were to tell you that they actually take 3 nanoseconds to turn, would you think that's an acceptable alternative? Because if you do, at least one part of your paradox is solved. Nothing stops immediately, even the ship that crashes into the planet will take a fraction of a second to come to a stop. Even if it's some sort of alien indestructable undeformable ship, the information "front end hit planet" will only travel to the back end at less than the speed of light before it can even "know" that it's supposed to come to a stop.
Anyway, back to the original question: if the ship stops (in some very small amount of time), the distance between a en b increases back to its normal value during the deceleration. In fact, the destination will suddenly be further away than it was before the ship stopped. Nothing wrong with that.
You have to understand what the word "distance" really means. It's basically nothing more than a difference in coordinates. You might measure a distance with a tape measure, but that tape measure itself might be contracted or expanded. It gets worse if you start measuring moving objects, since you can't even agree on what positions they were at at any particular time. Simultaneity is always causing problems, or rather, solving them whenever you think you found a contradiction. Google "relativity of simultaneity" to see how fundamental this part of relativity is.
So in order to define "distance", you have to agree on how you would measure this distance. Special relativity provides one way of measuring distances (using rays of light), while General Relativity can accommodate different ways of measuring. You just "tell" the theory "I would like to define the time and space coordinates in different places according to this formula" and General Relativity takes your definition into account. All that matters are the events that will happen, and they will be the same no matter which coordinate system you use.
For example, special relativity would say that, as you "look" further and further into the expanding universe, things are aging more slowly due to time contraction (the universe is younger) and they are closer together due to length contraction, so that the entire universe fits into a finite sphere with an infinite number of objects close together right next to the "border" which is just beginning to experience the big bang right now. I used "look" between quotation marks because I mean the infinitely fast way of looking you might use in a mathematical model without having to wait for light to get here (which would add more delay). Now, since this model is a bit awkward to use, most astronomers prefer a different way of defining the clocks everywhere in the universe so that the universe is the same age and looks about the same everywhere. General Relativity allows you to define time and space using pretty much any coordinate system you like, so why not? Now, the universe is infinite after all. The disadvantage of this model is that, at great distances, the speed of light is no longer the same relative to us. Light is pushed away from us with the speed of the expansion of the universe, and the light from certain distant places will never reach us because the universe is expanding faster than the speed of light. (In the first model, the light will never be emitted in the first place, because local time is moving too slowly, coming to an asymptotic standstill before the event even happens in our reference frame). Two totally different explanations with the same result: we will never see certain things happen in certain faraway places.
All of this is just to say that the notion of "distance" depends on definition. If you take a picture of the planets before and after stopping, they will not suddenly look like they have moved in time and further apart. If anything, they will appear to be closer (bigger) after stopping because of relativistic perspective effects. But you will infer that something changed with the local time and distances because you are now measuring the speed of rays of light differently, and any calculations you make from any observations after stopping will give different results for distances and times. That's because your mathematical reference for defining distances and times has changed from a moving reference system to a stationary one.
You can't extend your arm to touch the planet to find out how far it is. You can't use a tape measure while flying towards it. All you can do is, for example, send out a light signal and time how long it takes for the light to come back. And then you will come to the conclusion that a and b are further apart after you stopped. But lots of other things have changed as well! Clocks in different places are no longer running at the same speed, and they will even jump ahead or jump back during your decelleration. It's a miracle that relativity manages to still give consistent results when all these variables have changed so much.
It all only makes sense once you put it into a formula and figure out that, no matter which perspective you take, it all ends up not contradicting even if your gut says it should. Any actual event (like "this comet will hit the planet at the exact time that the clock on the tower right next to the impact will hit 12 o'clock) will take place no matter what coordinates you use, but any other subjective values (what time it will be on your own clock, how far away everything is) will be different. That does not matter, only the events do.
You only get paradoxes if you think about things like "the distance suddenly changed" while in fact, if you make any kind of experiment with those old and new distances, the results will never cause any actual contradictions. The problem is with you thinking that "distance" is some fundamental value while in fact it's just a variable that depends on what kind of reference system you happen to be using. Coordinates are only a means to the end of figuring out what would happen if you did some particular experiment. With different coordinates (like the ones you were using before and after stopping), the numbers will change but the results won't.