Right now all transactions are public. The block chain grows 'forever' and 'exchanges' are the weak link. Each node must also cope with growing bandwidth requirements.
What we need is a means for Bob to pay Alice without a central server and without a block chain and in 'any currency'.
It would be possible today to 'pay' for a good anonymously by joining the service's mining pool. Mine enough shares on behalf of someone else and they give you the good or service you requested with 0 transaction history.
We can use this 'mining to pay' method to make a decentralized anonymous peer to peer payment system.
Suppose a Service exists that will pay users $1 for each hash found below a certain threshold and that same Service will find hashes for others for $1.01.
Bob wants to buy a computer from Sam for $1000. So Sam asks for work from Service at $1.00 and gives it to Bob who pays Service $1.01 to calculate the hash. The service returns the hash to Bob who gives it to Sam who gives it to the Service who credits Sam with $1.00. The process repeats until 1000 hashes have been found and Sam ships the computer to Bob. Later Sam asks Service to withdraw the $1000 he has 'earned' by solving hashes on behalf of Service.
Now all that is required is for multiple people to set up 'cash for hash' services that operate in different currencies. People make money by arbitrage between different services. Buy hashes in $USD and sell hashes in BTC or Gold. Get work from deepbit, sell work to bitcoinpool...
There is now no 'currency' exchange going on, people are simply buying and selling CPU time.
Different hashes would have different values based upon the 'difficulty' of the hash. At any given moment in time there is an average number of GH/s available and a 'demand' for transactions will cause people to bid up the GH/s to speed up their transactions. The 'cost' of the transaction is the 'energy/network' cost to generate a sufficient number of difficult hashes plus what ever 'spread' is necessary to make things profitable.
It would be impossible to 'store' this currency except as 'credits' with other people/services whom you trust. It is like trying to 'store' your labor. You cannot do it and must convert it into something else. In this case, our CPUs are providing the labor. They sell their labor at a bit more than electric cost.
The currency is infinitely divisible by adjusting the denomination (difficulty). The supply is limited by available computational power. The demand is only for transactional purposes.
At any given time there is a limit to the amount of GPU time available and a fixed cost for running those GPUs at full speed. This means there is a limited amount of hashes at a particular difficulty that can be found in a period of time. If you view a unit of this currency as a fixed percent of total GPU time, then when a customer buys a computer, the merchant will 'sell' GPU time and the buyer will 'buy' GPU time. In this case, the seller will ask for work earning $1/hash and pass the work on to the buyer who will either do the work or buy it from someone else. Generally speaking, the work will be difficult enough that the buyer must buy it from someone else because it would take too long for them to do it themselves and it would probably cost more to mine themselves than for the optimized miners.
Everyone could create hashes, the issue is the 'time' involved in creating them. If the price is to find '1 bitcoin block in the next 10 minutes' then people will pay $1000+ for that much compute time. So everyone 'trades' compute time and it is entirely decentralized.
Initially this 'hash cash' will be backed by BTC mining, but in the long run could be backed by any 'password' cracking or 'collision searching'. Bitcoin is currently at around 5 TerraHash/sec which and the average 8 character password using A-Za-z0-9 could be cracked in just 2 days via brute force. I do not know how much people would pay for 'brute force' work, but I suspect there is a lot of 'brute force' hard to calculate, easy to verify kind of problems that could serve as demand.
In fact, I suspect that if there was no work like BTC mining, that people would 'make work' just to profit from anonymous, cashless, transactions.