Briefly, a variety of embodiments, including the following, are described: a system embodiment and methods that allow random access to voice messages, in contrast to sequential access in existing system embodiments; a system embodiment and methods that allow for the optional use of voice recognition to enhance usability; and a system embodiment and methods that apply to the area of voicemail.