So for now I've been messing around with Open Transactions. Although a server is trusted to process transactions, the server's power is limited. Eventually many servers will work in unison, storing your bitcoins in multisignature transactions to prevent one rogue server from stealing them. So it's not 100% decentralized, but this will improve with time.
One thing you can do is issue and trade your own "basket" currencies. For example, I can create a basket worth (1 BTC + 1 NMC) and sell them bundled together. This feature could really come in handy for predictions! Let's say I create two currencies...
(1 BTC if event X happens)
(1 BTC if event X doesn't happen)
... and then put them in an "event X" basket. I then sell these baskets for 1 BTC each. If Alice wants to bet that event X will happen, she buys a basket from me for 1 BTC and offers to sell the "doesn't happen" half. If Bob wants to bet event X won't happen, he can buy the "doesn't happen" currency from Alice. Once the statement reaches its conclusion, I place an offer to sell all the BTC 1=1 for the winning currency.
Advantages:
- Separation of powers between issuer and server
- Strong anonymity for bettors - even the bookie doesn't know what you're trading!
- Better resistance against hackers (especially once OT supports multisignature transactions)
Disadvantages:
- Bookies can still steal everyone's bitcoins and run away
- OT is still brand new and isn't ready for prime time yet
In theory one can create a smart contract for multiple voting bookies (to reduce the risk of theft), but I haven't quite gotten there yet. The important part is that this can be done right now using existing software, reducing the barrier to entry for all you would-be bookies who don't want to run a website.