For those wondering how you can undelete an ad, it's a feature available in the API. You can't do it through the AdWords web interface.
A related question: (Assuming undeleted ads don't have to go through review again.) If you add a new ad and immediately delete it, does it still go through review? I would love to be able to "pre-approve" some ads that way and be able to turn them on when I'm ready.