Let's look at Addr/PubKey B:
This is the easy one. There are three options here:
(1) Third-party gives you a single key to use on every transaction.
(2) You periodically download a new batch of 1000 publickeys/addresses from B to be used until you run out and get more.
(3) The application queries the third-party and requests a new addr/key to be used before each transaction is constructed.
Option 1 is clearly the worst, but it's the easiest. (If the service uses the same single addr/pubkey for every user, we don't have this problem, but that puts all users at risk if that private key is leaked...I wouldn't use that service)
Option 2 is probably the best, as it allows you to sync online or through an update packet every now and then, but mainly remain offline and sign transactions remotely. (This is most relevant for systems that are entirely offline that want to sign these transaction types.
Option 3 is the best for always-online services, but puts a burden on you to have internet and for the 3rd party to be available, just to send money via this kind of transaction.
The problem here is that if you pick option 2 or 3, you have to develop extra infrastructure to handle the communication of keys/addr between parties. Not terrible, but it's not trivial, either.
You have to do this no matter what. If you use option 1, you need a system to communicate your keys to the signing service, otherwise it won't know which user's policy to apply. If the system uses a fixed policy for every user, the attacker will just steal slightly less than X BTC per user per day, or whatever.
Also, you need a way to present the partially signed transaction to the service, so that it can finish signing it (if policy allows) and send it to the network. I don't think that you can avoid this step by using sequence and lock time, yet.
For Addr/PubKey C:
This is your key in your safety-deposit box. This is the part that's a little more difficult. The options are (1) and (2) above, because you can't query for a new address every time even if you wanted to. My main concern is that if you use a batch of 10,000 keys, you probably won't be printing the QR codes of the private keys onto paper into your safety deposit box (it'd be a lot of pages). But who knows what happens if you only store it on a USB key: you might get the USB key out of storage to find out the memory is corrupted. Sure, store the keys on multiple USB sticks and some ZIP disks.
This may not actually be a problem. Perhaps Option 2 for both can just store 1,000,000 keys/addresses and you'll never run out. But it is a concern/decision that will have to be addressed when this becomes a standard transaction type. At the very least, software developers might consider including a feature allowing you to store pools of keys/addr to be used just for this purpose. You would have a third-party pool, and a backup pool. You "fill" both of them when you start this kind of account and the client will automatically pull addresses from each one into B and C fields every time you want to construct this kind of transaction.
The emergency key is going to cause problems, no matter what you do. Most people that don't really care about anonymity will probably prefer to generate, store and use a single key C. The people that really do care about anonymity will want to make a new one each time, and deal with the hassle of storing it safely.
I really can't think of any way to avoid having to make the trade off. Mechanic's shops usually have a sign that says "Fast, Good or Cheap. Pick any two." I think we are going to need to think in terms of "Anonymity, Security or Convenience. Pick a linear combination where the vector sum is less than 2."
