Unfortunately assets placed in a safety deposit box are not covered under the Federal Deposit Insurance Program (FDIC). Unless the bank is found to be negligent in the way it handled or protected your safety deposit box, neither them nor their private insurance company will reimburse you for the loss.
Find out if in the duration you had your box with them, they moved, transitioned or merged with another entity. In this specific situation, you may be able to demonstrate negligence on the part of the banks as they have seemingly misplaced your box during their transition phase, and depending upon the value of the items placed in your safety deposit box, you may be entitled to some form of recovery.
Some homeowner's insurance policies may also cover the loss, but if you didn't document what you kept in the box, you have difficulty verifying proof of the value. Valuables are often lost but documents can often be reconstructed. You can get stock and bonds by paying a fee for new certificates. For wills and trusts, you can reach out to the lawyer that prepared them for a copy. You should always keep 3 copies of such documents.
When you put stuff in the box, always videotape it (photographs can be challenged) but if the video shows it was put in there, although it can still be taken out by you after you turn off the camera, yields more weight in establishing content and potential value. Also know the value of the items and check with your homeowner policy to make sure the default amount covers it, if not then you may need to include a rider to add the difference in value and the video, receipts, appraisals and such will serve you well in the future in such unfortunate circumstances.
If the contents of a safety deposit box are lost because you didn't pay the fee, then depending on the state you are in the time frame might vary (3 years on average), but none the less they are sent to the State's unclaimed property/funds department. You can search for these online often times or by contacting the state. It would help for you to find out which scenario you are in, their fault or yours, and proceed accordingly. Good luck.