I asked this question a few days ago (thread: Android Voice Answer 'Machine'
) and with a bit of help found Hullomail.
There is a free version (with ads) and and a paid version (exactly the same but without ads) and it is brilliant. For all those who scoff at users who don't have free voicemail, some of us don't - and have to pay for it. This app is great and does exactly what it says on the tin.
As Nick-B says, it will answer your call if you can't take it, play a standard (or recorded) message and will send an mp3 message directly to your phone. You then have a list of missed calls with the number of the sender, along with the 'voicemail', take them in any order, play back as often as required - or even keep them.
Great app - BUT .... I think that it only currently works in the UK.