I have never composed from my visual voicemail, but I just went into mine and tried it and had no problems. If you have uninstalled the software and reinstalled it; there is a good possibility it is the device. Have you synced your device with your pc? If not now would be a good time to do this. (this will back up and restore your information.) You'll want to insert the blackberry tools cd first and follow the insturctions. If you don't have the phone for business, click individual (or whichever option is not enterprise) 
Once your phone is all backed up (contacts, texts, e-mails, applications, etc . . . will be backed up) go into your options and go to security options and click General Settings, click the blackberry menu key and choose Wipe Handheld. You will have to enter Blackberry to do so. this should fix it. If not, visit a VZW store and they will exchange it out for you and you don't have to worry about them transferring anything over, either