I am not saying that at all, am I? I am saying DO BACKGROUND CHECKS. If the previous company says "He hasn't actually done any work yet" you would have avoided the problem.
I can't tell you what to do differently because I don't know what you are doing. But I can say you can catch him, and others have caught him, so why can't you?