In my company and my previous company, and the interviews i went through, you are required to fill out a form that with the information they want to check, such your degrees, schools, working history(including companies, titles and salaries), criminal history andcredit report etc. And you have to agree, sign it and authorize the company to check them before they will move along with interviews. And there is a line in the form, you will see that if they find any discrepancies, you will be fired at once, even if you are hired.
As a matter of fact, last fall my company fired an employee that has a domestic violent record. He didn't mention it in the background check form. After he was hired about 2 months, the company found out and fired him immediately.
So as a suggestion, not only be patient, also control your temper.