What is your current workflow for identifying wrongfully deleted records and appending them back in? Is the workflow scripted already? If so, how long is it taking that you need to invest more effort in speeding it up? If not, I would suggest scripting it out if you already have a workflow that works.