We must go in from time to time and run nbrbutil to see if NBU has a lock on any resources it should have, and if it does, we'll release the resource by running nbrbutil -releaseDrive <drive_name> or nbrbutil -releaseMedia <media_id>.

We have not really dug into what causes NBU to hang onto these resources when it shouldnt.

 This is happening on a constant basis.  yes, I did run that the first few times that we encountered the problem, but now its happening so often that it does not seem as a solution.  

What I think is happening is that NBRB is broken.  Support does not want to acknowledge this, but its the only logical explanation.  And if you stated that nbrbutil helps out then i am only convinced that my theory is right.   

Apparently, there is a recursive lock on the nbrb database that is potentially causing the issues.   

i too doubt it to be nbrb database stale stiuation, better to reset the database, it will clear all the state info's and release the resources.

nbrbutil -resetall
nbrbutil -resetmediaserver <media_server>

first stop all the backups and deactivate all the policies, then excecute nbrbutil -resetall from emm server.