This. I have never gotten a satisfactory answer to how centralization is prevented in such cases.

Vote with your (imaginary) citizen token to appoint a notary. And have a right to vote against it at any time. With blockchain you can elect new notaries every day if this is how you want to manage it.

How many votes does it take to appoint a notary?

If one or a few, I can set up a corrupt notary (or several) to notarize my fake deal with you.

If many, I can't get rid of the corrupt notary (or notaries) you have set up to notarize your fake deal with me.

Is either of these particularly great?

I don't see your point. You attack an outline of a system. Fun system will be complex and I won't describe it here in full. In the same way as today notary appointment procedure is complex and involve multiple organisations.

I claim that blockchain solves Byzantine generals problem (BGP) in a scalable way and no other such solution exists. I also claim that this very problem (BGP) is being solved right now in multiple instances by using a trusted middleman, usually appointed, controlled and often funded by the government. I also claim that maintaining trust is not free and often paid from tax money (as in DVLA example). And my last claim that partial or full automation of a middleman function with blockchain is cheaper than running it traditional way (considering all costs involved).

Potentially unexpected corollary from the first and second claims - a software without blockchain cannot automate a trusted middleman function because of trust issues.

Feel free to attack any of the claims.

Why would I need to attack any of your claims, when one of them is that the "problem" you cryptards are getting your panties in a bunch about is already solved?