There's no fixed duration for how long deleted voicemails stay in the "Deleted Messages" folder. It's best to check this folder as soon as you realize you've deleted a voicemail.