Slightly more seriously though, I think for the Proof of Storage idea to pack enough punch to be a deterrent, you'd need the cookies to be quite large. Is there a way to avoid needing them to send you all the bytes each time? Because that will cost you (the site owner) too.

I had the idea of sending requestors a challenge like "Flip the bit at position i of the large chunk of stored data, hash the result and include the hash in your headers". Instead of the site owner keeping the full stored data, they would just keep the RNG seed used to generate it -- this saves on storage, though it still requires them to do the same time-consuming hash computation done by the requestor.