1. A method of providing playback of an audio voicemail message corresponding to a visual voicemail message; comprising: receiving a voice call at a voicemail system directed to a called party device; storing an audio voicemail message at the voicemail system; sending a copy of the stored voicemail message to a transcription service; transcribing the copy of the stored voicemail message into a text-based voicemail message; embedding the text-based voicemail message with a unique identification for accessing the stored audio voicemail message; sending the text-based voicemail message to the called party device; at the called party device, receiving an instruction for playing the stored audio voicemail message at the called party device; from the called party device, calling a directory number associated with the unique identification for accessing the stored audio voicemail message; and in response to calling a directory number associated with the unique identification for accessing the stored audio voicemail message, playing the stored audio voicemail message at the called party device.