[p4bl0]

Is the point of the service to allow anyone to send voicemail to any email address? Or is it for people who own the email address to allow anyone to voicemail them?

Because in the latter case (which is what I think the service is), you could make the users register their email address (using a verification email to ensure they do not register someone else email without their consent) in your service and then have a map from a random hash to the email, allowing you to provide urls looking like dialzoo.com/nzef1824Ldaw68873 rather than forcing user to publish their email in clear. Or even require a username and use that for the URL.