When creating notifications for thier apps, developers can set the FLAG_NO_CLEAR flag to indicate that the notification shouldn't be dismissed when the "Clear All" button is pressed. This prevented the notification from being dismissed from the notification panel by the user, but Android still allowed this flag to be cleared programmatically. This is what permitted apps like Clear Persistent Notifications to remove "persistent" notifications, while still retaining notifications for "ongoing" events (which would have the FLAG_ONGOING_EVENT flag set instead).
However, with Android 5.0 (Lollipop), Google have changed this behaviour so neither of these types of notifications can be removed programmatically, and changed it so only the app that posted the notification could remove them. This poses problems for Voicemail notifications, as the network message to remove them could be easily missed by the phone in regions of poor network connectivity.
The only way to get rid of them afterwards is to open Settings -> Apps, navigate to the "All" tab, then find the right app named "Phone" and force close it. There are two apps with the same name, and about 5 with the same icon, but only one of them gets rid of the voicemail notification. The phone app would simply restart itself so no phone calls would be missed, but the notification would be gone.
Several of our users who have upgraded their devices to Android 5 find the Clear Persistent Notifications app doesn't function correctly any longer due to these changes in the Android API. In an attempt to address this issue, we have updated the app so launching it on a device with Android 5 or higher would automatically open the correct version of the phone app. All you will have to do is to hit the "FORCE STOP" button, and the notification will be gone. The app would still function normally on pre-lollipop devices.
As always, all feedback is welcome.