The voice mail system is controlled by your carrier.
If the voicemail messages were stored on the carrier's servers, you need to contact them.
If you previously saved your messages to the phone as MP3 files (or whatever), you might be able to recover them using some of the methods for "undelete my files".