How to recover deleted voicemail from iPhone 4S?
If you did actually delete the voicemail, a new cell should have appeared if you scroll to the bottom of your voicemails.



Then, tap on Deleted Messages, and you should get this screen:



Now, tap on the voicemail that you would like to delete, and press Undelete:



Hope this helps!