I've had this problem almost since the debut of Kit Kat. In that time, I have had multiple Nexus 5's, one carrier-locked from Sprint and one completely unlocked from the Play Store. From activation on Sprint, both times, I have had a non-dismissible notification reading "New voicemail (2) / Dial ___-___-____" and I can't seem to tie it to Google Voice or anything in particular at all. The only simple fix I could find was Mario Zumbado's (which works fine for a few hours at a time but is still extremely annoying to have to do) but a month or two ago I came across a solution that told people to do something along the lines of decompiling their OS/Google Dialer, finding a single line of code, and changing a number from "02" (whatever number voicemails were appearing) to "00". A bunch of people on that thread said that it worked, but I had just sideloaded Lollipop and I didn't want to try anything risky, so I didn't. I'll look for that one and come back if I find it.