You haven’t mentioned in your post which version of Veritas Backup Exec you are running.
I know you stated that you checked to ensure that the server had the backup remote agent installed. But did this mean you checked that the server from which the backup is being perfomed on had it installed or does it mean you checked the remote server/workstations that you are attempting to backup had it installed? The remote computers need to have it installed on them in order for you to back them up correctly.
Another module you hopefully have is the open file option which allows you to backup files that are currently open and in use or else files that are in use at the time of backup, will most likely get skipped over and end up not being backed up.