Ok, do a quick search for "Voice Inbox" for the Nokia N95 - that'll give you an idea...
This may be possible once the SDK is released, but i wonder if someone could write some code, to effectivly answer an incoming call, play a greeting then record the message onto the phone.
Someone has already managed voice recording, next step would be to record the call, and then work out how to take over after say 20seconds.
On my N95 i turned my voicemail off, and had Voice Inbox setup to answer after 20 seconds.
A possible alternative for those without visual voicemail.
The app would have to have the option to be included in some kinda startup list, and also would ideally be able to place an "active" icon some where.
N95 version...:
Voice Inbox
an iPhone version of that would be awesome!