When I worked for a telco, you could easily call the voice mail main line, and then just use options to leave a voicemail in any mailbox. Easy peasy.