Voicemail Issues?

[ghsDUDE]

So I'm on Verizon and I have the 4S.

I noticed that to get Voicemails (or make the notifications show up) I need to restart my phone and then they're there.

I had 2 important ones yesterday that didn't show up until today after I restarted my iPhone. Is there a fix for this?

 

[ghsDUDE]

I just restarted my phone and had another voicemail.

What the heck?! I got it around 3pm today and after I restarted it (around 7pm) it shows up.

Should I take it in or is there a fix for this?