Safety deposit boxes are a great idea. The problem in my area is a severe lack of supply. I've been to quite a few banks in the area and have yet to find one not already rented out, at least at the banks with which I do business.
This is true. I've gotten lucky at a couple banks and came across the large boxes. I've come in at the right times or the wrong time depending on how you look at it. The large boxes are usually kept for years by an individual and usually means if one is free that someone sadly just passed away. Nonetheless look for new bank that is opening up and get in early.