I just got the Droid Charge and in my area there are some LTE issues too. Around my house I have no LTE but less than a quarter of a mile in either direction I have LTE coverage. I have a ticket open with Verizon.
Google Voice provides free Visual Voicemail. All you have to is download an app for your phone and change your voicemail provider via a special code you dial. -- Tom