Hello 
I’m having this problem too: the notifications in the lock screen always show ‘new voicemail’ but everytime I call there is no voicemail there. It’s annoying because when I am on a train and go into a place with no signal, then out again, it constantly chimes to say I have a message. It’s being sent from the Phone app and I’ve tried turning notifications off. Help us!