NATO stock numbers and the "old" FSN (federal stock number) should be similar. They added a double-digit sometime in the 1970s as I recall regarding a lot of that.
When I was in the Navy, the supply department had hard copy (and were slowly moving to microfiche) of manufacturers' part numbers to FSN, but I don't remember there being an FSN-to-description document. In any case, I suspect that by now, every bit of that is computer-driven, either on CD-ROM or available by authorized parties over the Internet.
The GSA used to have a lot to do with that system, so maybe nosing around that direction would be helpful.
Dean