Did he make a backup before doing the check run? Restoring that backup would be the easiest way to get out of this mess. If not, I'd strongly recommend getting your Adagio consultant to help out, the steps to untangle this will be numerous.

Then, turn off the ability to Void Checks - it's a setting in the Company profile. You should hardly ever "Void" a check. If he had Reversed the checks, everything would have been OK.

Also, consider using blank (rather than preprinted) Check Stock. Blank check stock makes it impossible to print on the "wrong" check stock since Payables generates the MICR and other bank information as the paper goes through the Laser printer.