Lose anonymity and bring back key-signing parties. Maybe you can't guarantee that everything is human-generated, but at least you know the chain of trust that leads to the human that signed off.

Yes, I'm aware of the irony of creating a darknet that only works by removing anonymity.