I don't know what kind of voicemail you're referring to, the one provided by networks over here just sends the caller to voicemail if you don't pick up, you will get a text later.

There may be a different voicemail service where you live (visual voicemail?) that I have no experience using.

Then there's Call Screening that android had indeed been had for a while, but it doesn't record a message, it's a back and forth interactive conversation and you can see the transcript in real time.