I've heard of a good idea to prevent this (besides captchas), which is that if a user/bot needs to be rate limited, the service starts to require a small proof of work task to be done, something that would take a typical device a few seconds.

If you have a genuine need to post something, waiting 5 seconds is not a big problem. But if your goal is to spam 1000 of something, now you need to wait 5 seconds between each post, and the task can be made progressively harder so that by item 1000 it's a 5 hour calculation rather than 5 seconds.