Early apologies if you see this a little late - we've been married exactly one year now and the champagne might get in the way of uploading this issue everywhere. Time flies when you're having fun.
Undelete an iPhone Voicemail Message
There's no Command-Z in the Phone app, but you may be able to retrieve a deleted voicemail message: Open the Voicemail screen in the Phone app. At the bottom of the screen, tap Deleted Messages. To restore a listed message, tap it and then click Undelete.