I have gotten a notification that I have 1 new voice message. However, I am in a different country right now and would rather not pay an exorbitant amount of money to call my voicemail just to dismiss the notification. Is there a way I can remove it without calling voicemail? I have tried restarting the phone and swiping the notify away, but it's a pretty persistent notification.
Try sliding the notification bar down, then long press on the 'New Voicemail' notification. There should be one option "App Info", go to this and clear cache and data.
If your version of android / device doesn't support the long press notification, go to
Settings > Applications > All > Phone 'phone' may be called 'dialler' or similar on varying devices. Clear cache and data.
Warning some devices (very rarely to be honest) tie your contacts to the Dialler application, or your call history, clearing the data may clear some or all of these. Ensure you have backups to be 100% sure that, however unlikely, if something goes wrong you have what's important. It's VERY unlikely and I do this all the time to get rid of that notification, but it's always better to be safe than sorry.