Got the same issue. I have cleaned the voicemail box and even disable the function with the server.
has instruction on removing voicemail notification alert but in OneUI 3 Samsung made some changes to call settings and I don't know how to clean its cache and data
Not sure if you have already resolved this but for any others searching I had the same issue with a permanent new voicemail notification when adding a second SIM on my S21. When I called up it said I had no new voicemails.
I tried clearing app data, cache, force stopping and restarting the phone with no result.
I phone up the carrier voicemail number (O2 for me on 901) and it gave a number of options including how you are notified about voicemails. The one it was set to was display by on-screen notification (or similar wording), I then changed this to be notified by SMS (text message). The on-screen notification instantly went away.