So how is it that a power failure would cause the voice mail password to change?
That is stored on the hard drive, or flash memory.
Power failures only affect the programming translations on an ACS processor, and that's what the AAA batteries and Backup/Restore card are there for.
Are you having trouble logging into the System Administrator's mailbox, or personal user's mailboxes? If it is PVM card mail, and the mailboxes were changed from their default assignments, AND a factory default was not performed prior to the initial programming, that perhaps could cause you not to be able to log into some user's mailboxes after a power failure.
Please give us something more to go on. As Joe asks, which voice mail are you using? And which password has been lost?