I work in software for a payroll processor and the "duplicate" SSN problem comes up all the time.
First off, we're not the employer and really don't care who you hire -- that's your problem. I think your contract with us requires that you perform verification of your employees, but we don't handle it. Give us an SSN, and we'll put it in the system.
Secondly, we *legitimately* see duplicate SSN's all the time in our database. Most common? Someone holds two jobs at once and we do payroll for both employers, for example.
Or, a worst case? Jane Smith works at ABC Company on January 1. She gets married on February 1, changes her name legally, moves, and gets a new job. Her old employer "lays off" Joan in case she comes back. February 2 she shows up in our database as Jane Doe at a new address, new job, new name but the same SSN. Both employers saw legitimate documentation and neither has knowledge or a duty to inform the other of any of this -- nor does the employee. We are bound not to disclose this to either client (confidentiality). What do we do? The quarterly filings contain completely different Janes, with the same SSN.
This is someone else's problem.
Now the State and Feds have this file that contains a "duplicate" SSN -- and they know it. What can they do, short term? They've got to swallow the file and take the withholding money. They're so far downstream from the problem, the best they can hope for is to send a notice to the employers asking "WTF" or kick Jane out for an audit when she files. The employers will both say she's fine. When she files -- a year later -- she claims both incomes, properly. Everything is okay for the IRS.
TLDR: SSN is a *terrible* indicator of uniqueness, and the IRS can't find your illegals for you.