Dial 123 from your phone. Then enter your password followed by pound sign.
Choose 5 from menu to access advanced options. Then choose 1 to record
message. Hope this helps.