Perhaps its time for a centralized theft registry.
Yes, this will reduce the pseudo-anonymity but it can be done.
Here's one possible way for bitcoin-wallet services to handle things, but it's off-the-cuff so it's probably buggy:
Through the use of multiple wallets and a central registry of "stolen bitcoins," a wallet service's customers can put money they don't need immediately in "vaults." Unauthorized "withdrawals" from the vault will be refused by the software and will never make it into the block-chain, thereby providing some protection to the funds and deterring wholesale theft from bitcoin-wallet services.
Give account-holders two "wallets" - a "pocket money wallet" and a "vault wallet" - and create a third wallet - a "holding wallet" - that is controlled only by the wallet service.
Wallet #1 is the "pocket money" wallet. It has no additional protections. It's used for "petty cash" and for money that will be needed in the next day or two.
Wallet #2 is the customer's "vault wallet." For certain customers with few incoming transactions, this "vault wallet" will be stored "offline" and only moved online temporarily when the customer tells the wallet service there will be an incoming transaction soon.
Wallet #3 is the "holding wallet" for Wallet #2. There may be more than one such "holding wallet."
The "vault wallets" are registered in bulk by the bitcoin-wallet services with a central authority. Only certain transactions are allowed "out" of these vault wallets. All other transactions will be refused by the software - they will never make it into the block-chain.
If an exchange is compromised, all of its "vault wallets" are considered compromised until the exchange indicates they are not. Transactions indicating withdrawals from these "vault wallets" during the time of the compromised are refused by the software - they will never make it into the block-chain.
The registration is nothing more than
* some identifier belonging to the wallet service, to ensure that the registration information isn't tampered with later
* the identifier of the "vault wallet"
* the identifier of one or more "holding wallets."
* for each "holding wallet," a minimum time between each transaction. This will usually be at least a day.
* each "holding wallet" will typically be automatically dumped into the customer's "pocket money wallet" when the time expires.
* at the wallet-service's option, additional obfuscation may happen after the money leaves the holding wallet and enters the customer's "pocket money wallet." For example, the money leaving the customer's "holding wallet" may be dumped into "bank's temporary wallet #1" and an equal amount transferred from "bank's temporary wallet #2" into the customer's "pocket money wallet" shortly thereafter.
* at the wallet-service's option, the "holding wallets" may be part of an obfuscation scheme. For example, they may be randomly re-used across customers, or they may be designed as one-time-use wallets.
* a time-delay for any registration information changes other than marking wallets as compromised.
The idea is that the "pocket money" wallet is just as vulnerable as ever, but it will rarely have most of a customer's coins in it.
The "holding wallet" has some vulnerabilities but it will be empty most of the time and thanks to the "time lock" it's unlikely that all or even most "holding wallets" at a given will be able to be stolen at the same time.
The "vault wallets" are protected enough to make the immediate reward of "raiding" an exchange much lower than it is today. There will still be theft, but the number of people interested in stealing from exchanges will go down and the risk of loss from a given theft will go down.
* This is not a complete solution.
* There are probably anonymity issues I haven't considered.
* There are new denial-of-service issues introduced by this system. I can see the possibility of a DOS attack against a particular "vault," against a particular "wallet service," or even against the "central registration authority" itself.
These issues will need to be looked at and either fixed or deemed "acceptable" before this or any similar system will be accepted by end users.