How often are they queried, and what percentage of the payment is the punishment?

A bad host could only store, say, 1/3 of the data that they say they are, and play the odds that they are storing the requested random chunk.