Perhaps the relays could be, each one, a line in the hashed message and so long as the hashed message included a line of text provided by the relay, it can confirm the user did unique work, without requiring the user to hash each message independently. A single message could be hashed and used as verification but still only once for each relay that provided, each, a line of text to hash.
Discussion
Doesn‘t this go a bit against thin relays?
There's far more messages than users and each user would only be working on one hash for each relay at a time, so I think it's within the same order of magnitude of storage space required as running a relay and storing a constant 1 additional bit of text for each user.