We now have found the reason of our problems: if a job that backs up more than one drives (or servers) cannot connect to the first drive but successfully to another one in the line, BackupExec resets the set counter for storing the backuped data. Thus BE starts to overwrite all stored data (or at least the database entries used for identifying the restore selection). Thus from the point the counter is reset, the corresponding tape is no longer usable for restoring the data backuped so far.
As an example consider a notebook user that connects his laptop to the network just at that time the backup job starts to work - to late to connect to the first drive, but accurately timed for backing up the second drive - this will reset the set counter and make the tape unusable for restoring data stored so far.
We perform the incremental backup of our notebooks in one job at the same time each day - everytime the first notebook is not connected to the network and BE can successfully connect to another one, BE resets the set counter.
As a workaround, we now backup a small file directly from the backup server at the beginning of each job - this guarantees, that BE can connect successfully to the first drive and we have no problems anymore. We do this for each job because we want to avoid that a reboot of any server at the wrong time will corrupt the backup data of a whole tape.
From our point of view this behaviour is definitely a bug in the Veritas BE software.