In the universe of Star Trek: Andromeda, ships are given a construction assignment number that eventually becomes their registration number. However, because the runabout USS Allegheny is numbered NCC-7900 does not mean that it is the seven thousand nine hundredth ship that Starfleet has commissioned. You see, spacecraft names are 'attached' to their registry number for a time. When a new keel is laid for a given name, whether due to peaceable retirement or violent death, a letter is added to the terminal end of its registry. This, of course, has to happen only a limited number of times or we would still be in the low three thousands. After seven ships, the registry number is changed. To honor the crews and keels that came before, the line "Successor to the Starships <Name>, NCC-<Number>" is added to the dedication plaque of the new ship.

In our timeline, series of ship refits are numbered in Roman numerals. Using this system, the NCC-1701-A would be a Constitution II-class ship. In the same vein, the NCC-1701-B would be an Excelsior II-class. The NX-2401 is technically an Excelsior III, however it largely retains the outward appearance of the Excelsior II with a few 24th-century modifications.

With the authorization of the sector commander, a reassignment of ship's name and registry can be performed. In such ways, the USS São Paulo NCC-7563 can be made the USS Defiant NCC-1764-D. There is, yes, the potential disparity between a given ship's exterior markings, interior displays, and IFF beacon. In these cases, the IFF broadcast is to be trusted first until communications can be established to assess the ship's identity.

We have also managed to solve the eternal dilemma of the registry code prefix. It's really quite simple. Every letter stands for something, but is not necessarily an initial of the word it stands for. This fine, time-honored tradition is taken from such fleets as the United States Navy, where CVN means Carrier, Nuclear.

Federation Ship Registry Prefix Code Chart
Letter First Second Third
A Unknown Foreign Privately-Owned Cargo Transport
B Romulan Planetary Defense Space Station
C Klingon Starfleet Naval Vessel
D Ferengi Corporate-Owned Unpopulated Platform
E Terellian NGO-Owned Passenger Liner
F Gorn Administrative Aerospace Forces
G Cardassian Engineering Transorbital Facility
H Tzenkethi Commercial Training Post
I Breen Hazardous Materials Impulse-Only Craft
J Tholian Maintenance Special Weapons
K First Federation Derelict Drydock
L Preserver Highly Mobile Dyson Sphere
M Dominion Warp-Capable Niven Orbital
N Federation Science Proof-of-Concept
O Borg (RESERVED) Spherical
R (RESERVED) (RESERVED) Research Vessel
T Trill (RESERVED) Torpedo Boat
X Experimental Experimental Experimental
Z Unknown Unknown Unknown