Starting with v9, backup exec won't even connect to a ServerOS machine unless there is a RemoteAgent installed and running (BERemote service), unless they are accessed via User Defined Shares, which is generally done only when the agent CANNOT be installed (like on a NAS box)
Would both of these files been off the same backup , or different backups?
If they don't charge you for restores, try submitting some test restore from random days of the week back as far as they say they keep the backups and tell them that if none of the restores are succesful, you want a full refund.