> Proof is hard

I would argue that it can be made much less hard. Vast majority of cases can be verified by online presence, phone calls, domain emails etc. Minority of cases, like locksmith, are not easy to verify. In those cases you impose proof of work. Meaning that those folks must perform extra work which makes it expensive for them to keep repeating. For example, you can charge them $100 to run third party background check, require them to give TINs and other LLC documentation etc.