Having a problem w/ 3.4.1 and handling media

The site I'm at has several ATL P1000 robots.  Every once in a while I'll
run into multiple 96 errors (can't find media)  The problem is that there
is recycled media in the jukeboxes that are not associated w/ any backups and
therefore expunged from the netbackup database, but the jukebox won't select
any of them.  

If I run a bpmedialist on the mediaid in question it states that it 
can't find it (which is good).   However if I run a backup for the same
media pool that this media ID is associated with in the volume manager database
It will not select that media, and will instead state that there is no available
media and report a 96 error.

Does anyone have any ideas? I have a script which crossreferences the tapes
in a jukebox with the bpmedialist command, and I'll get several tapes that
should be usable, but still recieve a 96 error.  Perhaps there is a database
entry that I am missing.  
-----------------------
Nicholas Pesce         |
System Administrator   |
Ericsson Wireless Unit |
Ph# 858-332-6140       |
-----------------------