I just figured out how to fix my voicemail notifications. I had this notification stuck for months. The voicemail number has changed. I got my phone reactivated by the way.
I first cleared the voicemail app data then I made a call from another phone leaving a message. I then restarted my Fire Phone and waited. The notification never came back and 15 minutes later the new one showed up which I called in and deleted and that notification went away. So I can use voicemail again.