You may also want to look at this thread [1] where I suggested to prevent double-spending by requiring several (at least two) signatures on a tranaction. The first would be from the paying party, the others would be from 3rd parties who would just confirm that the transaction is not part of a double-spending scam.

[1] https://bitcointalk.org/index.php?topic=189697.msg196627