I posted this basic idea awhile back on the -dev list, but Gavin's recent "UltraTransactions" post reminded me about it again...
So as we all known establishing reputation anonymously is very difficult. However, if you could provably, publicly, spend coins at a net deficit to you, with the transactions cryptographically traceable to your identity, you can establish a value for the identity that will be destroyed if tarnished.
Option 1: From an address you control, spend coins to an unspendable address - 1111111111111111111114oLvT2 is a good choice.
Option 2: Create transactions that spend coins to miners fees. These transactions will have to be numerous and consecutive; if not someone with control of a decent amount of hashing power could simply spend coins in blocks they themselves mined.
In either case the identity, even in the face of pruning, becomes the merkle paths from the transactions to the blockchain, allowing future proof that the transactions happened from an address you control. (of course, using that identity is now a matter of signing statements with the private key of that address)
Option 1 is very simple, and I see no security flaws in it. Option 2, while nice from an encouraging network security point of view, is more problematic. For instance, aside from the consecutive problem, if this idea becomes popular in theory we could even see large mining pools collaborating to to reverse blocks where this has happened. You could keep the fees per transaction low-ish, but then the required number of transactions, and the size of the identity, becomes huge.
Now, you've got an identity, great! Lets suppose you're operating a trusted bank, for, say, zero-conf transactions. Ideally what we want is a fully automated way of distributing proof that the identity has violated trust. For instance, if you want to send money to someone, the bank will sign a "letter of intent", stating what the bank will do. Now if the bank fails to send the money, or refund you, you create a machine readable "violation notice" and publish it. The bank can undo the effect of this notice by proving that it did what the letter of intent said it'd do, for instance, by providing transactions showing that money was transferred as requested. If it can't do that, everyone can choose to do no more business with that bank in the future, destroying the trusted identity.
The trick then is, how do you publish these notices? You need a persistent log of every violation made in a given type of trust domain, while at the same time preventing griefing like publishing lots and lots of spammy notices. Again, requiring a provable expenditure to publish a violation could work. Similarly if every violation really is properly machine readable it might be enough to just have nodes validate them and move on. You're also going to want to prevent finney attacks somehow... although in general, information is much easier to copy than censor.
There is also another issue: going back to the bank example, how do you know if the total deposits exceed the value of the identity? One way would be for the bank to do all transactions through a given address (or a deterministic wallet) and expect people to audit the block chain, although that has the issue that certain types of services, such as anonymity providers that resend pools of coins become more easy to track. For non-bitcoin applications this is even more difficult; essentially you've got the same "what happened?" distributed problem that the blockchain solves in the first place.
In any case as a first step creating a protocol, even for human verification, would be valuable; people can always bitch on bitcointalk if someone screws them over...