Factory default the PC Card Voicemail - if you have set any passwords to other than default, you'll find that they also are reverting to default after a power failure.
Known condition on some units shipped from Avaya without being defaulted after initial testing. Also finding that after they've been in service after a number of years, mailboxes start doing dumb things like reporting they are full where there are no messages in the box.