That assumes the same salt and passphrase were used to produce all your paper wallets. If it were one salt per page, or one salt per address, that wouldn't be the case. If each address had its own salt, and you knew that you needed to redeem salt+passphrase, then you could do that (for example) directly on MtGox (which allows redemptions of arbitrary strings as private keys, which it converts via sha256 to a 256-bit value).
I think I was probably using the terminology wrongly, mixing "keys" with "wallets", etc.
the paper wallet (with no private keys) could also have a single salt string printed on it, where the salt and the memorized key are required to regenerate the private keys
That's the part that made me think a single salt plus the passphrase would give up all the private keys in the wallet in one fell swoop.
But if the salt was long enough to not be brute-forceable, and each address in the wallet had its own salt, that could work nicely.
If you have to have a unique salt for every address, why even bother being deterministic... That's not deterministic anymore.
I was picturing the paper wallet page having a text box at the top for a secret key. You put that it and it encrypts all of the private keys with the same key. This should be quite simple to do.
I would probably print one unencrypted page for a physical safe, then enter a key to encrypt all of the private keys and print that page out to keep in my desk at home.
If I use one of my paper keys on a compromised computer, I don't want to lose all of them. Non-deterministic wallets should guarantee this.
