I don't care for the "Naval Construction Contract" idea either, though of course it is "official" (though not necessarily canonical) as described above.In this old discussion, someone always brings up that modern-day organizations such as militaries have tons of registry letter prefixes that seem either to be based on nothing at all or to have had their origins lost to time and circumstance. It is fun to think of what the letters might mean, but their reason for being there in the Trek universe might be innocuous, outdated or even arbitrary.
I can do without "naval construction contract," myself. That word "naval" in there seems sorta out of place, not being used very often in the rest of Trek to refer to the ships or fleets. I encourage fans to keep making up their own meanings, but not to quote them as if they were fact to people who innocently inquire as to the origins of that "NCC" on the hull.
I prefer to think of it as a transponder code. Every ship flying broadcasts a basic "IFF" type code. The marking on the side of the ship is visual confirmation of the same code being broadcast.
I'm partial to "NCC" standing for "navigational contact code," but some others have (not incorrectly) pointed out that the various other variations don't necessarily fit with that.
SO... every ship does broadcast a navigational contact code, but "NCC" doesn't NECESSARILY mean that... it's just the prefix code first used. The Federation has since expanded the codes list beyond that, so "NCC" now means NOTHING. (Very much like DVD now means nothing. Originally, it was "digital video disk" but due to some lawsuits, there is now no direct connection between where DVD came from and what you're supposely allowed to call it today.)
In any case, every ship has its transponder which broadcasts this signal, allowing other ships to be aware of your identity and status without having to keep a tracking scanner beam on you every moment. Obviously, if engaging in stealth operations, you'd turn this off, but that would be pretty rare for Federation ships, I think.
This fits with the approach I prefer, but also fits nicely with MJ's take, and actually gives a rational explanation for the similar-but-not-identical takes we see with NAR, NX, etc.
At some point, someone decided that all experimental ships should broadcast a special transponder code identifying them as such... and by committee, they decided that "NX" just sort of "felt" like "experimental." So they added this into the mix.
Maybe they then decided to expand it to include "all resource carrying starships." The debate would have gone back and forth, probably leading into sub-classifications for various resource carriers (fuel, basic cargo, foodstuffs, ore, whatever)... but eventually came back to a single classification for "all resources." NAR.
Something similar might have happened with NSP. Perhaps it means "Small Patrol Craft?"
Granted, once established, the "original intent" of these things often falls away (remember, we're talking POLITICIANS, not rational beings here!) but initially, the "expansions" of the navigational-contact-code system probably meant something to somebody, huh?