Do you have cellular data turned on? Visual Voicemail requires it; VVM doesn’t work with just Wi-Fi.
Do you have a 3rd party VPN installed? If so, delete the VPN profile in Settings/General/VPN & Device Management/VPN. Don't just turn it off; delete the profile. If that fixes it, you can try reinstalling VPN.
Have you tried a forced restart:
- Press and quickly release VOLUME UP
then
- Press and quickly release VOLUME DOWN
then
- Hold the SIDE button until an Apple logo appears (15-30 seconds), ignoring "slide to power off" if it appears
The operative word here is QUICKLY; and try it a couple of times, the timing is a little tricky. If done correctly this will always work unless the phone has a hardware problem.
If none of these work Voicemail is a carrier feature; you need to contact your carrier.