It depends on what option you have set in Tools | Option | Media mangement
if you have the option to overwrite sratch media first then then it would overwrite the media which is in sratch media set .. IF yoou have the second option selected here --overwrite recycleable media ==then When you submit the in job which as to overwrite the job would look for overwritable tape in the media set where the backup job is targeted if it does not find the tape then it will look for new tape in sctrach media set . if there is no new tape found then it would look for the overwritable tape which is older ,
read the following document http://support.veritas.com/docs/192265  this would give a better idea

Mine is set to the second option.

From the document which you suggested.

Backup Exec first searches for recyclable media in the User Media set targeted in the backup operation. If using an autoloader and more than one recyclable media is available for the backup operation, Backup Exec will select the media based on the number of hours the media has been recyclable (media that have been recyclable will be chosen before media that has just turned recyclable). If two recyclable media have been recyclable for the same number of hours, Backup Exec will then select the recyclable media based on the lowest allocation date or time

In my case, Tape B has a lower allocation date, yet it is ignored.  Since my tapes are not appended to, their allocation dates are the dates they were overwritten.

Its strange !! how frequent does this issue happens ... Run the inventory Job before the backup ...  MAke sure you dont have partitions created as if the backup job is targeted to specific partition it will look for tape in that partion itself  and will not run on tape which is in another partition ..

This is the first time this happened with this media set.  I have another media set, but I did not noticed this behaviour.  I have saved the tape info and I will see whether Tape B get used tonight.

The Allocation date is linked to the Append Period and defines how long a tape can be appended to. When a tape becomes overwriteable links the end of the last job that wrote data to the tape to the overwrite protection period - as such the tape in question may have still beeen overwrite protected when the job started that appeared to select the wrong tape.

So I guess the real question is what were the Modify dates on the tapes, when did you backup job start that used the wrong tape and what is the overwrite protection setting in your media set.

The tapes in the media set are not appended to.  My job is set to overwrite, not append.  Thus the allocation date is the same as the modification date.  They are moved off-site the next day so they can never be appended to.

Last night, that tape was again ignored.  A newer tape was used by the backup job.  I will be taking this up with Tech Support.

I forgot to add that my library is not partitioned.