I've had my Curve 8330 (Verizon) for about six months and have never received anything resembling a proper voicemail notification. About 4 out of every 5 times I receive a voicemail, I receive a garbage text message that reads something like:
on your previous phone, did you have any kind of email acounts setup on it? I got the same messages when I switched to my curve. Turns out I never deactivated the sprint email app on the old phone. I had to reactivate the old phone and deactivate the sprint email app.
You email was added to the app tho. You would have to delete your email account from the app. If you still have the phone, that's your best bet from my experience.