First of all, do you have a password to the admin mailbox? It is 4321 by default...if you're talking Partner MAIL or VS. Start by looking at the phone system and the cards in the slots. A VS is a PC card in the processor slot, a Partner mail is one of the cards in the system with part numbers and designations.
From the admin box, you can remove and add VM boxes. That's the quickest and easiest way to clear it out.
Look around for an 8 1/2 by 11 book about 1/2 inch thick. It's the manual to a 4.1 Partner Mail. It will have worksheets in the back of the book on how to set up the Auto Attendant and selector codes (routes for digits dialed).
If you don't have a manual, comment back and I'll get you a link to Avaya's manuals. I think
www.avaya.com is pretty well shut down to the general public.