If they paid into social security, it was with the use of someone else's social security number. That would be a crime. 

They always say that, but to prove it, they would have to reveal that they used illegally obtained social security numbers. More likely they were paid under the table cash wages and paid no taxes. Until, of course, they learned about the ITIN and that they they could game the system by claiming all their nieces and nephews as well as their own children (real or ficticious)that supposedly lived with them for 6 months and a day so that they could defraud the taxpayers out of even more money in the form of child credits.

I want E-Verify to be the law of the land and I want these people on street corners with signs begging for money to have gainful employment. I want people who apply for ITINS and drivers licenses to be required to prove they have legal status to be here.