One can easily establish a pseudonym and furnish it with a public key. If the corresponding secret key is used with care the reputation of the public key can be protected Bootstrapping the reputation of a public key should be difficult, however.
A bondsman for pseudonyms might accept anonymous payments accompanied with a public key. The bondsman would hold the money and publish a bond; to whom it may concern. The bondsman would be thus commissioned to judge conformance to digitally signed contracts. The bondsman would be judge and jury and make decisions for a cost of perhaps 10% of the bond.
The bondsman would have a reputation to protect with both classes of customersthe bonded and the service buyers.
I can imagine a bond for as little as $50. The bondsman would be required to make a snap judgment in case of conflict. Repeat business with both the bonded and the buyer would be required to make this economical.