It is the keel a maritime vessel that is laid down first and this is what retains the name if the ship is rebuilt toa new design, evn with new frames as the original keel will remain.
Therefore, it is possible to totally rebuild a starship to a new design yet retain the original NCC number despite the new name, as some part of the original keel and space frame are incorporated in the new build.
It happens in the current modern and past ship building for sea going vessels, so why not for starships in the 23rd century.
A typical example is the world's first aircraft carrier, HMS Argus, which started out as a naval collier, back in the 1900's. Another is one of the Japanese carriers from WW2 was a reworked cruiser.... with a different name.
The trend for NCC numbers to be reused is more like an acknowledgement of a starship's life history.
As for the Klingons, much honour in battle has been won on many warships and this is valued.... so most old hulls are rebuild into new technology designs at the end of their service life.... aka the D4, etc.