What if the fee were respective to the user and not all users where the cost to submit a new batch of messages is exponentially more expensive than the last?
A third, less flexible solution may be to put a hard cap on the amount of times a given user can submit a new batch of messages.
Both of these could be applied to publishing single messages as well, like you can only change keys so many times.