Obviously both parties are at fault here -the teachers and the school. The teachers started the fraud, the school let it fester and become infected. Teachers who buy fake degrees, as far as I am concerned, have zero business calling themselves anything but liars. Schools who keep such people on staff, as far as I am concerenced, have zero business calling themselves anything but scams.
As for how to solve the problem, it is as easy as drafting a document for ALL teaching applicants to complete and sign when they first visit the school that specifically authorizes the release of the required information and explaining that any applicant found to have engaged in educational fraud will be immediately dismissed for cause. Let the candidate know via e-mail or in a phone call a day or two BEFORE the scheduled interview that he will be asked to sign such a document when he comes for the interview, and that the school does check the authenticity of all degrees, and those who have reason to fear will not show up.
Having a candidate sign this up front (and of course making sure you actually do the check) shows you mean business and will weed out most if not all fakes. The no-show rate with no call or courtesy e-mail is already more than 50% during the interview process, and this will just give the people who are not truly qualified for the jobs being offered another reason to shut off the alarm and sleep off their hangovers.