If I continue the logic of your reasonning, the employer should have a technical test the candidate needs to perform in order for the employer to ensure that the candidate is not simply lying about his competences. If the employer gives the test, the employer hires him because he succeeded, then it is more the employer fault to hire him in the first place, not the employee fault because he performed the test.
The moment a person becomes a citizen of a country, he is entitled to the exact same right that the citizen next to him. There is no distinction of a citizen who was born in the country vs a citizen that was naturalized.
In your case, if someone profits from a lie, then we correct the process so that people cannot profit from it anymoreinstead of revoking things you gave by mistake (things _you_ gave by _your_ mistake).
If you hire someone without checking that what they say is true, then I am sorry but you're just stupid. If a country give citizenship to people without verifying that what is written in the application is true, then I think the process is incredibly stupid.