I think at this point that this guy has lied about literally everything in his background.

I would check his legal name, citizenship, whether he got the GED he claims, residency, etc. He's a congenital liar, not an "embellisher."