WaxMail requires a small download and a quick installation with Outlook. From there, all you have to do is click a button to record a voicemail. The sound file is saved as an MP3 and is attached to the email, which can also include text and other attachments. WaxMail is free, although there is a small text advertisement added to the email. For those wishing to exclude the add, WaxMail charges a $29.95 one time fee.
The downside is that it only currently works with Outlook, and I really dislike Outlook. The upside: it’s free, it works incredibly well and it has a very slick interface. Also, I love the fact that files are actually sent as attachments (meaning they can be listened to offline, easily forwarded, etc.) instead of forcing the listener to click on a link. Check out Jason Clarke for additional information.
Try it out and send me a voice message at firstname.lastname@example.org
UPDATE: Robert Scoble just discovered WaxMail as well and has some ideas on using it for podcasting.