Isn't this why there are trial periods ( no idea if it's a thing in the US with the "right to work" thing)?. Over here in the EU a work contract can't be terminated from the company just like that, there needs to be a specific reason ( like downsizing, or a serious error), and you can't quit just like that a mandatory notice period is required ( of course negotiable depending on the situation), usually in the 1-3 months range. Therefore there's a trial period at the beginning, 3-6 months usually, during which any party can end the employment with a very small notice ( a day or two).
So if someone lied their way through interviews, in the first couple of months you should be able to detect that and terminate their trial period.