I have the same issue. It's been there for a few months now. I went through TMobile support and they couldn't figure out why. They said maybe with a future software update, it might correct it
My voicemail notification is dated 10/18/18. It's now been 1 year and yet still no way to clear. Hate to say it but the notification will almost definitely persist beyond the usefulness of the watch.
I ended up going to a TMobile store. I'm not sure what he actually did, but it was something like disconnecting from the network then adding it back like a new device.
I’ve had this once or twice. I’d suddenly start getting repeat notifications of an old phone call. Notifications every hour or two for a 3 week old call. To clear it I had to delete the call from the recent logs on my phone.