What are some proposed solutions to a decentralized marketplace so far?
One solution is to use Nash equilibrium in order to force people to cooperate.
The concept is quite simple. Both the seller and the buyer make a deposit.
If the entire buy/sell process goes fine they can recover their deposit, if it don't they both lose their deposit.
So it isn't profitable to go away with the money without sending the good nor to get the good without releasing the payment to the seller.
This solution has already been discussed. If you google bitcoin+nash+equilibrium you will find more informations.
Another way is with an arbitrator and multi-sig addresses. Payment is made to a multi-sig address where the sender, receiver, and an arbitrator each have a key. If the transaction goes well the sender and buyer each sign. In case of a dispute the arbitrator rules and signs either with the buyer to pass the money on or with the sender to return the money.
We are currently using notaries as a third party in a multisig transaction with arbiters serving as dispute resolution if there is an issue. You can read more at: https://github.com/OpenBazaar/OpenBazaar/wiki