But voicemail implies storing the audio somewhere, and that means cost.

And at least in my country one should explicitly enable voicemail. I never could make it work for some reason..

And as far as I can see, it is not widely used.

EDIT: Oh, I completely missed the fact that there can be a fake voicemail where the phone automatically answers and asks the caller to speak and record it and store the audio on the phone itself. Then the user can check such recorded messages later..

Did you mean something like that? I am really surprised that this is not common already...