Right, that all makes perfect sense, and I agree. In essence if you're selling an item like a firearm you give up all rights over it, including any privacy expectations -- consenting to any search the new owner wants to have done into the history of that gun.
However, the possible issue I theorized would be more plausible in the case of that random phone call from Joe Public to run the numbers on a gun you don't (and for all you know, HE doesn't) have. You really don't know the circumstances and he may be legitimately checking on an item for sale, or just Billy Joe trying to stir up trouble for his neighbor Earl by copying down a serial number on the gun Earl just picked up for cheap, and fishing for something to get Earl in trouble over. Weird as it may be, that search may not be consensual. Possibly still not an actionable 4th Amendment issue, but another reason why departments may not simply leap to offer such services to anyone who calls.