There's plenty of theft-protection that is already available, and will be available if users are willing to put in the time to use it. It prevents theft in the first place, rather than recovering from successful theft.
(1) Cold storage (see my sig). Online threats become nil once you have your private keys offline, then only physical access can compromise the keys
but the service must be able to do the transaction automatically.
(2) Multi-sig: all funds can be setup to require 2 or 3 signatures, which can be kept in geographically separate places, or one of the keys can be based on a passphrase.
With both in place, only the select few that are supposed to have access will be able to use it. Cold-storage by itself is a 99% fantastic solution that many of these services are not leveraging, either enough, or at all.
It is a sufficient solution for me if I need 2 separate computers that do NOT communicate with each other to confirm initiate the transaction. But if the transaction is conducted in one place by inserting two keys in one wallet, or by confirming the transaction with a passphares ... this is not safe enough.
I don't really care if most of the thefts occur due to ignorance of the service provider. A popular service (like mtgox) is probably the target of many intrusion attempts and after some time people will break in.
... in any case I will read more about the dual signatures ...