Sure.

First, requirements are low:
Allowing the BitSpender (spending BTC on stuff) to choose his Gift Basket solves many problems (USD quantity transacted, anonymous use of name/identity/address, specification of merchant/product-version, etc.). The software then requires only the ID of the Gift Basket (a few characters). The website chosen (Amazon, NewEgg, Walmart, etc.) does have access to everyone's info in a connected way, but they do not know that they are party to a Bitcoin transaction, so you can safely use their existing centralized infrastructure for the non-Bitcoin parts. This infrastructure includes private wish lists, shipping/tracking numbers, proof of payment invoices.

The Bitcoin requirements are also mostly low: BitSpender pays 1% of order upon creating the 2 tx's (2 of 3 multisig, one for success, other for cancel/refund). This 1% can be easily verified as a database-entry requirement, invalid entries will chase away counter-parties. If either everything goes well or parties mutually agree to cancel, they simply sign the relevant tx without any new requirements. The reputation system I envisioned was simply a total of all USD volume (easily calculable from the shared database, and possibly even reconstructed completely from the blockchain's shared history, if embedded with OP RETURN). Disagreement statistics ("reputation") can be easily calculated (how often arbitration was req'd, for which transaction sizes, what was the outcome, etc).

Something like BitMessage, which you've already discussed as a shared database idea, can probably handle all of these requirements so far. We also considered BittorrentSync despite its closed-sourceness.

Second, we initially planned to be the centralized arbiters, collecting all the 1% fees for ourselves. However, over time we expected other people to become arbiters and compete with us on fees/service/volume.

Thirdly, I separately developed a math trick (in Truthcoin) that allows people to vote on an arbitrary obvious Yes/No external state, with a Nash Equilibirum of them each voting honestly. Its difficult to translate this math trick into the signature world of Bitcoin transactions but I have some ideas that might make it a little easier if the specific application were known.

Notice, for example, that arbitration is very easy because Amazon/whoever will give receipts. Faking them would probably be too much work for a scammer. Honest individuals could establish long-term reputations and leverage this reputation into better prices. Honesty could become its own industry.