I don't know how the different state requirements operate, but in general it would be very difficult, if not impossible, to trace one back very far. Regarding original sale, remember it has not been that long since NOTHING about a gun sale at retail was recorded on paper, at least in most states. You paid your money and walked out the gun shop door, no questions asked, just like buying a candy bar.
The most likely scenario would be if one of your guns was siezed for some reason (say an arrest while you were carrying it), and a subsequent LE check showed it as having been stolen by running the SN. And I have no idea how far back such a check can go, assuming a stolen gun was even reported to LE and placed on some database. I'd guess many stolen gun SNs are never placed on any database, as many if not most gun owner theft victims probably never recorded what their SNs were and so do not know.