Assuming you were using the encryption mode that is part of Backup Exec versions 11D or greater then this was designed so that if anyone managed to somehow steal your media that there would be no way to restore without knowing the password. If you are using this typre of password (passphrase) then I belive you need either the passphrase used to create the encryption key, or a copy of the Backup Exec Database files from before your hardware problem to enable the restore of your data,
There is a way to accidentally end up with the old style media passwords enabled even though you ware running 12.5. If it is this type of password there is still no way to decrypt the password, (
http://support.veritas.com/docs/267323 ) but the data iself is not encrypted so a data recovery company might be able to help.
The causes for this scenario are in
http://support.veritas.com/docs/325611
As far as I know you get a different error state for this type of password compared with the encryption type.
Note you can ONLY end up in this state if the server was originally upgraded from Backup Exec 10D or earlier. If it was not an upgrade then you are stuck with full data encryption and there would be no point in going to a recovery company as they will not be able to recover the data.