I'm assuming you rebooted the phone system. This will, by extension, also reboot the onboard voicemail card. From the sounds of it, though, I believe you are fighting a losing battle. Brown-outs are the worst thing out there for electronic equipment and it sounds like a new card may be in order. If you cannot connect to it via PC, then you won't be able to connect to it through the phones. I strongly suggest getting the phone system on some kind of battery back-up to help protect against these kind of instances.
Wish I had better news. Good luck!