Fusionmoth certainly knows what he's talking about so hopefully he'll be able to help you.
i rembember how painfully annoying this issue was for me so i can empathise, honestly!!!!
i inserted my sim in a mates phone and found that the voicemail icon still showed up on theirs!
whilst the sim was not present in my phone there was no issue. put the sim back in, a ***EDITED*** voicemail icon popped up! in my case, this made me realise the problem had to be with the sim and not with the phone like BT were trying to tell me!
this is the only light i can shed on this unfortunately and i apologise if it's useless information.
I hope you get some answers for the sake of your sanity!!!
With my experience in mind I'd just get them to send you a new sim. If it worked for me i can see no reason it wouldn't for you.
Good luck! 🍀
I am delighted to report that the replacement Sim has solved the errant Voicemail notification problem where all else failed! There is a God!
According to the forums, this seems to work every time so it should be written procedure.
Regards David Porter (porterdavejp)