I don't already work with a vendor that supports AVST I would suggest Black Box Network Services, as they are high level certified for the majority of the major PBX vendors and the AVST platform. I don't know where you're from, so I'll give you the number for my Milwaukee rep, and she can help you get to the right office if you want to get a price quote. Her name is Michelle Ball and the number is 262-798-2375.
As for all of your requirements, I am using all of that right now. Unified Messaging is your ideal solution for the message delivery to E-mail, but I know you can to E-mail notifications of new message arrival and attach a .WAV file to that message. The catch there is that you will receive a copy of the message and the original will still be in your mailbox to deal with. In true UM when you delete the E-mail with the message it will be removed from your mailbox as well. But the notify way is free and some of the UM ways have a fee per user. There are about 5 different ways to do message delivery in AVST.
For auto attendants, that is driven by how many ports you have configured in the system for your call volume. An auto attendant is basically just another form of a mailbox. You can select how many ports can be used for notifications, outdials, incoming calls, etc, so that is pretty flexible. I am running mine with 24 ports and about 700 user mailboxes and that is enough for me. My system has direct inward dial though, so most of my calls go direct to desk without first hitting voicemai, and voicemail only answers if the person is not available. The rest of the stuff I use for customer menus to direct them to different areas and departments' etc. I have not used all 24 ports at once yet in over 3 years.
Vacation stuff is pretty easier from your desk and even easier if you set up the mobile apps. I believe the mobile apps are all included in the purchase, but need to be run on a webserver such as IIS or Apache.
The system is also very configurable for redundancy and the ability to spread out the system servers over several sites if needed or wanted, and it has your choice of 5 different telephone user interfaces so you can pick the one where the button presses most closely match the ones you have now.
Hope that helps a bit. It can't hurt to call and ask for the literature and docs on the system or have them work up how much it's going to cost. I have quite a bit of licensing and features set up on mine and I think it only ran around $65K someplace. Your mileage may vary. you can also go to
for product information as well.