This kind of problem is exactly what the PGP "web of trust" attempts to solve.

Perhaps that technology could be reused - people who wish to join the web of trust can publish a PGP/GPG key and every person who successfully trades with him or her can sign it.