The first thing that occurs to me is to decentralise the database, which incidentally is rather a computer-ish concept. Each person designates two or more Keyphrase Holders, with a separate password for each. For low-security situations, they have to give their passphrase to one KH; for maximum security, they have to convince all of them. Ten or a dozen passwords should not be beyond anyone's memorisation capabilities in a world without shiny Internet distractions, and the KH can write them down - this gives you a lot of different DSP-DPs instead of one big one. Any given KH may be suborned or have his database broken into, but by the time you get up to a dozen or so that is unlikely.
Obviously this works best if you don't have to physically drag the KH to the prison cell, or whatever, before you let the innocent one out.
To make this easier to memorize and more secure, you could have there be a much larger number of KHs. Their job is to be KHs; their identities are kept secret even from each other. Each KH has a certain property about the person's password that they learn- e.g. its length, the number of vowels, the number of times the letter "a" appears minus the number of times a letter appears, etc. However, they don't know the password itself; they only know the person's answer to the question. When a person wants to be released, a certain number of KH's, ran...
If it's worth saying, but not worth its own post, even in Discussion, it goes here.