Mt. Gox and Tradehill are performing the functions of an exchange, a broker, a non-bank depository institution, a clearing house, and a stock custodian. In the real world, those functions are usually separated. (Sometimes they're not. See
Bernard Madoff. That didn't end well.)
A completely distributed exchange is quite possible. You first need some way to do an atomic transaction in two commodities between two untrusted parties. One approach is to split transactions into tiny ones, each one being done separately and completed before the next one starts. That way, any rip-off is limited to the size of one transaction.
Once you can do that, you just need a way to broadcast "buy" orders. Only one side needs to be broadcast, although it's useful to broadcast both. Orders can't be anonymous, since you have to know who the other party is to deal with them. If you see a buy order you like, your client contacts their client and does a deal. First client to get through wins.
There are some problems. Transactions cannot be undone, except by mutual consent of the parties. There can be no "rollbacks". Any gains from market manipulation stand. (So you had better have enough cash reserves to handle a mistake now and then.)
A party can broadcast buy orders but not respond to matching sell offers. Since orders are not anonymous, this behavior is detectable. You need a reputation system to kick out traders who do that. (Which is exactly how live commodity trading floors dealt with it.)
Lag is a problem. Network transit time and local processing delay affects your trading profitability. (This is a problem in real-world trading. Look into "high frequency trading" and the efforts made to cut lag to microseconds.)
It's not as orderly a market as a system with centralized processing of limit orders, but that's the price of a distributed, mutually mistrustful system.
