Voicemails are not stored on your phone. They are on your carriers server. Thats why you can access mobile voicemail from any phone by calling the voicemail number applicable to your provider.
Did that answer your question?
Although there are probably solutions for that too.