Scampi has a good idea to bring the maintenance staff together to gather what they know. If previous records of the preventive maintenance work were not deleted, look to those as a template. Your currently existing maintenance staff should have experience in doing preventive maintenance, they will be key to rebuilding the program.
A PMP is going to be very specific to your site and equipment, basically the goal is to perform scheduled maintenance on your equipment to ensure it is running optimally. The specifics of these tasks are sometimes described in the technical manuals for your equipment.
And yes...it's standard practice for IT departments to have a daily-backup system or some kind of data-recovery. Users shouldn't be able to just completely delete records as they see fit, your system should be permission-based with the highest functions reserved for IT staff only.