Not sure if it will work but the usual suggestions are to reset/restart/restore your iPhone and/or try dialling *228 and choosing option 2. If the problem persists you might need to contact VZW to make sure there isn't an issue on their end.
I'm having the same issue on my 4S. The only way the phone will tell me I have a voicemail is if the phone is rebooted. I rebooted it this morning for an unrelated reason and got a notification of an unread voicemail from Friday (this is now the following Thursday!). I'm a new customer to Verizon as of Oct 15th, so this is not a lingering issue from switching from another phone or anything like that.
I have a trouble ticket with Verizon, now over three weeks. Having same issues and Verizon does not have resolution at all. They advised me that I need to switch to another phone, other than the iPhone 4 until this is resolved. They also will not let me out of any contract with Verizon. iPhone is great, Verizon has many issues.