There's a new startup called Jott.
Basically, you call a number, they transcribe what you say and then send it to you in an email. Unfortunately, the messages you leave are transcribed by humans! (privacy, scale issues)
Here's what Jott's CEO has to say about it:
jotts are completely anonymized to transcribers. They do not know your account name or other information.
Perhaps they should just reroute calls through Vista's voice recognition. It's probably the first widely available voice recognition implementation that's up to the task.