Had this issue start a few weeks back. Been driving me nuts. I've cleared caches and done restarts, basically everything I know how for this particular app. Today I broke down and went to tech chat app for asurion. Lady there told me to go to the dialer and dial *73 to make sure the number hadn't been forwarded. I told her I never had forwarded my number and thought it was a waste of time but I did it. I was amazed when I called from my wife's phone and got the regular greetting instead of mailbox full. Left a message and instantly had the icon pop up in the top notification bar. I pulled it down and hit it. It was like nothing ever happened! All my voicemails that I never knew I'd gotten for the last 2 weeks were there.
Please try this and see if helps in your case. It was the very first thing they recommended so that tells me they've seen a bunch of this lately.
1 other thing that bothers me is that the vm settings for the note 20 ultra do not give me the option to automatically archive voicemails like I could with my note 10 plus. The voicemail app version on the note 20 ultra is 13.000.10 and there's no option to uninstall updates for it.. the app version currently running on my older note 10 plus is 13.1.00.1 and there is the option to uninstall updates when you tap the 3 dots while in the app info page.