We already do have such vaults. At least most traditional banks in Europe have storage vaults for their clients. e.g. you can lend 1 usually quite cheaply, e.g.

We already do have such vaults. At least most traditional banks in Europe have storage vaults for their clients. e.g. you can lend 1 usually quite cheaply, e.g. 60eur / year. A bank teller is always present while you're making a withdrawal, and you need 2 keys to open your vault. 1 key from the teller, and 1 key from you. The chances of this kind of vault getting robbed is very, very slim. If you're worried about that, you can BIP38 encrypt your paper wallet's private keys, so its impossible to use them even if paper itself is stolen. There is also some chance that the vault will be struck by a flood, earthquake etc. For that, I recommend using a USB as a back-up, where the keys are encrpyted using truecrpyt etc, and the physical drive itself being kept in a very secret location, ideally located in a different city than the bank vault itself, so that the chances of being affected by the same disaster as your vault is minimized. This is almost a failproof setup in my opinion (you can worry about loosing your Bip38 or truecrypt encryption keys, or what happens if you die etc -- there are good ideas about how to deal with these kind of circumstances as well, e.g. write a hint for BIP38 key which only you or your family may understand on the paper wallet). So best place to store your wallet might very well be your good old bank, ironic enough.