Subcontractos who have an employer ID number are legal to operate, if under a company name.
However, an individual tax payer iD number, which is obtained using a W-7 and referred to as an ITIN, are not valid for employment. So the person may not work under this number. This does not matter if it is federal law or Tennessee law.
Only a valid Social Security number is XXXXX for employment purposes.
A business operating under a business name would required an EIN number.
The rule is, that you have to make sure the persons you hire have an I-9 form completed.
If you are hiring sub contractors from another company, your only requirement is to ask the contractor if he has I-9's on the employees. AND you must do that for all employees, not just the one or two you suspect of not being legally here.