phone has nothing to do with it, it's stored with the carrier and it's probably gone. If you were the NSA or it was a high profile case, it could probably be retrieved from backups, but normally, once you delete it, that space is free on their server for new voicemail and it's gone.