An idea that I don't have the time for, so I gift it...
One disadvantage that Bitcoin has over banks is that at the end of the month the bank sends me a statement and I can see what I spent my money on. This is convenient as I can store it away, don't have to do any work myself at that moment but can still do my accounts years later.
With bitcoin, if I don't make a note of what any particular transaction is at the time, then I will have no clue in ten years what I bought. All I'll see is an address. I guarantee that most people are not disciplined enough to write appropriate notes on every transaction they make; and even if they were, bitcoin does not compare favourably with their bank if they are forced to do so.
So, could we create a distributed "receipt" system, shopping cart interfaces would, upon payment from a particular customer, know what bitcoin transaction hash paid a particular invoice. Could that information be published to a distributed database (a centralised one would be fine too)?
Of course people don't want the details of their transactions being published for the world to read, so the receipt database would encrypt the incoming report (or the shopping cart interface can do it for extra paranoia) using the address(es) in the transaction (which are nothing more than public keys). The only person then able to decrypt those details is the owner of the private key that matches... i.e. the person who spent the coins.
Bitcoin clients could query the receipt network when relevant transactions are received, decrypt the message and copy it to the local log. Being that the message is copied, the receipt server doesn't need infinite storage, just enough to give people who want the facility long enough between client runs to grab the data.
Voila: automated bank statements from Bitcoin, but completely secure, completely distributable.
(I think ECDH + AES can be used for this)