Wise declining the shop when you're unsure about the legality. I wish more people were like you. Too many people trust that "reputable" companies do everything by the book. Truth be told, they don't always. And if you wind up doing something illegal, it's your ass that's going to jail.
As for your question, see Flores-Figueroa v. U.S. The SCOTUS ruled that in order for identity theft to occur, the defendant must know that the SSN belongs to another person.
I'm taking that they're supplying you with a fake number (probably starts with a 9) that they programmed their system to decline when they find it. I don't know if this is what they're doing, it just makes sense. If this is the case, you don't have much to worry about it.
I'd find out more information, though. You have a legitimate concern. I don't want to say one way or the other whether or not it's legal. You're wise for not doing these shops until after you've researched it, though. Props.