If you need to enforce changed passwords every two weeks, why not just set in Class of Service, Password Expiry to 14 days? Why delete mailboxes and make everybody record their name again? People would also lose any settings they've personalized, as well as their greetings. I think the approach you're looking for might be the wrong tool for the job.
With that said, the rest of the post may give you some more insight on how you might accomplish what you're describing.
"When I call in to get messages or to change my greeting I press ** so my assumption is that some combination of keys could be used to get <feature> or the other three buttons."
I understand what you're thinking, however, the system can't be programmed via touch tone, and there is not a way to add and remove mailboxes while calling into your voicemail remotely. There isn't a DTMF tone for Feature or for the soft-keys, and you can't dial in with a modem to your voicemail, so that won't do either. The only way to access the programming with a phone is with an actual nortel set, in person.
However, if you figure out your voicemail type, there may be something that can be done. I've successfully put our Norstar Voicemail 4.1 on our NAM on our local network, so I can use the Norstar Voicemail Manager (a proprietary Windows app) to manage mailboxes. It even has an "Add Many Mailboxes" feature. With that working, if you wanted full automation, your next step would be to use AutoHotkey on windows to write a script to work the menus and buttons to do what you want.
If you're really lucky though, you have a Call Pilot which can be programmed via its built-in HTTP server. If you're a programmer, I'm sure you can imagine how you would be able to write a script to do what you want by using the curl library or similar to make many requests on the web server. Word of advice, it doesn't seem to be the fastest webserver ever (it times out from time to time) and it is running on a tiny little computer, so if you go this route, just do a delay of 2 seconds or so between each request you make on it to prevent overloading it. It would make the script take longer, but that's better than handling the exceptions when you start getting timeouts. Also, It could even be that hammering it might result in corrupting the settings.