You're right, that happens from time to time.
But by now the testdesigners are getting more careful. Our method in doing regressions tests for multiple cycles is to copy a tree with testsets and remove some old testinstances. That's much easier, than creating all testsets from scratch.
Be careful with allowing deletion of test lab folders (eg. can they delete folders with test sets in them? delete multiple releases at the same time?).
Also consider giving users who have delete access a more detailed confirm message (eg. "Are you sure? Deleting this folder will also delete X test sets, Y test instances, Z runs"). Once had an admin make that mistake and delete a few weeks worth of testing results.