Thoughtful, detailed coverage of the Mac, iPhone, and iPad, plus the best-selling Take Control ebooks.
 
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.

From Tonya Engst