I am looking for recommendations/links for a service that can give/assign me a phone number, have a recorded messages played when someone calls such as "press 1 for ..., press 2 for yyy etc" and then allow the caller to leave a message that is then emailed to the owner of the particular voicemail box.

Google voice works for 1 mailbox only, but something like that with multiple mailboxes and multiple email addresses would be great.