Re-upload all the voicemail files. (send_g711.bat <ip address>)
Then make sure you have option 1 in the AA pointing to DialByName.
Most importantly however, IIRC, there were some issues in 5.0.8 with the embedded voicemail that warrants an immediate upgrade. (Improper silence detection resulted in cut-off voicemails and the documentation to upgrade the prompts was not 100% so it resulted in some prompts missing. With 5.0.20 you can use "upload voicemail files" in the Embedded File Manager which is much easier.)