The problem comes down to our system is messed up.
The employer might suspect that somebody is an illegal but if they present proper documentation how are they supposed to know? And we specify what documents are acceptable and do not expect employers to detect fraudulent ones as asking that of them ends up being discriminating against immigrants, period, because they take the better safe than sorry approach.
And our system has a big problem with identity theft. Trying to enforce checks against a government database ends up with them working on stolen identities rather than completely fraudulent ones. You make the fallout worse. We need to back up and solve identity theft first--but we are doing very little in that regard. We get government obsession about every detail matching which causes headaches for a lot of people with minor flaws in their history (for example, the hyphen that snuck into my wife's name) but it does nothing about identity theft.