The paper doesn't explain this in the clearest way, but they do have a strong incentive to negotiate: they can capture some of the money that the debtor would spend on seignorage.
Suppose Dave owes Carol 5 francs, and that old franc coins contain 4 oz of gold, while new francs contain 2 oz gold. So Dave can take 3 old francs (= 12 oz gold), convert them into 5 new francs (= 10 oz gold, with the mint taking 2 oz gold in gross seignorage) and pay off his debt that way. But if Dave and Carol renegotiated, Dave could pay only 11 oz of gold, and they'd both be 1 oz of gold better off than if Dave had paid his debt in new francs.
I don't think that debtors in lenders were any better at negotiating in the middle ages than they are today. When you're a debtor, and you know you can get 'free money' by going to the mint, why would you bother negotiating with someone (a lender) who has an incredible amount of power over you.
If the quantity of metal was the origin of the value and they weighted the coin when using it, why they need the mint in the first place? why not to use the metal directly?
So, the solution to the puzzle is just that humans aren't actually all rational and well-informed?
