We have about 400 voicemail boxes.

Some of our most important issues:
-MWI not working for unassociated mailboxes at all, not consistent for associated mailboxes
-Voicemail delivery is delayed randomly for different mailboxes (will show up hours or days later)
-Advanced Unified messaging (with MAPI gateway) does not consistently integrate with Exchange mailboxes. It works fine for some, works partially for others, and doesn't work at all of others.
-Phones don't show a count of new messages. They will show "1 new message" regardless of the amount in the mailbox.
-After last upgrade, skipping forward and backward (* and # keys) only works intermittently (DTMF problem?)

Those are just the higher-priority things off the top of my head, I could add to that list.