Are you asking about voicemail greetings played to the caller? Messages left by the caller and played over the phone? Messages left by the caller and sent as email attachments.
For the first, convert the file to .wav, 8 kHz sample rate, 16 bit, mono, confirm that it sounds good in your editor, copy it to
(replace 1234 with the proper extension number)
and delete other formats of the file.
For message playback, set the desired format(s) at Settings -> Voicemail Admin -> General -> File Format.