Are you using an unlocked device on Verizon? Many devices not branded to Verizon are not capable of using Verizon's visual voicemail. I had to call Verizon to block both paid and free visual voicemail in order to stop the exact same thing you're seeing. Now I just use traditional voicemail.