So you create a paper wallet. On the way to the bank, a super-government-spy-satellite reads your code. Or your bank's security is compromised or you just get lazy and leave the paper wallet on your desk and you have a break-in and it gets stolen. All your precious bitcoins are now gone.
So how about instead of creating a wallet, you create a transaction which can later be put onto the blockchain and will send the coins to a specific Bitcoin address? The transaction is signed so cannot be altered or redirected to another address. You don't have to worry about the security of your bitcoins so much because any potential thief not only has to compromise the security of your bitcoin storage but
also of your target wallet (which could be a paper wallet, of course). I'd imagine the process something like this...
Store1) Software generates wallet. RAM only if possible. Displays public address.
2) You send funds to public address.
3) Software generates transaction for sending funds to your target public address, does all necessary signing, converts to QR code (or whatever your preference is) and saves/prints/whatever.
4) Software wipes & deletes wallet
Redeem1) Scan/convert QR code.
2) Paste here
http://blockchain.info/pushtx .
3) Wait for confirmations.
Thoughts? Has this been done before?