Do Not do any kind of reset if you want to get something back on a phone. A reset will wipe things, not get them back.
Voicemails, however, are you stored on your phone. So you would need to contact your carrier/service provider to see if they can be restored.