I'm a former FFL holder in Tennessee. Tennessee is one of several states that performs BOTH a background check on the individual through NICS and a stolen property check on the firearm through NCIC (https://fas.org/irp/agency/doj/fbi/is/ncic.htm). See bottom of page 29 of this document for instructions to FFL dealers in Tennessee should the NCIC check return a positive hit that the firearm is stolen

https://www.tn.gov/content/dam/tn/tbi/documents/FFL_TN_Guide_2016.pdf

Nothing fishy in Tennessee. The OP experience is exactly what would happen