mostly all sprint phone have this now. all the samsung M series have it.
it's not really a voicemail, its like sending a wav attachment with the recorded message..
basically its nothing more than recording something then emailing it.. this is something you can do with any phone i think.. the only difference is it sends it as a MMS i think.. the party receiving it has to download it.
the way
cozboogie describe is the real way to send a true voicemail without the party phone ringing but it only works if you both have the same provider as already noted.