With regard to the NCC-1701-A, there are three likely possibilities, none of which has ever been canonized:
- Fleet Admiral Morrow, in Star Trek III, makes it clear that Enterprise NCC-1701 was already seen as slated for decommissioning (although he gets the age wildly wrong). This is consistent with the ship's status in Star Trek II as a training ship. Therefore, it is possible that NCC-1701-A was already being built under that name.
- A new Constitution Class ship could have been renamed Enterprise to suit the occasion.
- A recently re-fit Constitution Class ship could have been so renamed.
In Star Trek V, Scotty does refer to the A as a "new ship", which seems to weigh on the side of 1 or 2.
In real navies, though, this is something of an aberration. Ships are planned years, sometimes decades in advance, and their names planned along with them. As one pertinent example of this, USS Enterprise CVN-65 has beenwas retired for years and is being dismantledin 2012, although it'sbut was still nominally in commission while it was being dismantled, only being finally deconmissioned in 2017. However, CVN-80, the next planned holder of the name Enterprise, has not yet even had her keel laid yetonly just (as if 2018) begun construction, and won't be afloat until at least 2025.
My supposition, then -- and I'll stress that this is just surmise, because we simply haven't been told, canonically -- is that NCC-1701-B was the originally planned replacement for Enterprise NCC-1701. The need to give Kirk and his crew a ship changed the plan.
We know very little, canonically about the NCC-1701-B or -C, but we know that the C was lost with all hands (plus one temporally displaced Lt. Yar) at Narendra III. The circumstances were thus entirely different from the loss of NCC-1701, where the (famous, high-profile) crew survived and giving them a new ship seemed the best way to keep them out of real trouble! There would have been no reason to accelerate the inheritance of the name from the -C to the -D if it was already planned to give it to a member of the next advanced starship class, even if that was going to be 10-20 years in the future.
NCC-1701-E, on the other hand, could be seen as a similar situation to the -A. Once again, a famous, proven crew had survived the destruction of their ship and needed a new one, at about the time the Sovereign Class was having its keels laid.