Here’s a half-baked idea for you: instead of voicemail (or in conjunction with), why not have auto responder texts. Basically, most of the people who call me call me from their cellphones so they can receive texts.
When someone calls me and I don’t pick up, the phone would look their number up in my phonebook and check if its a mobile number of a landline. If its a mobile number, it could just send a text to let whoever know why I haven’t picked up the phone.
If its a landline, there are services that use text-to-speech to turn the text into a voice message and then ring up the landline like a normal call and then read out the text.
Odds are I can find this idea on half-bakery.com.