Rate limiting can be achieved without actually inconveniencing regular users. Put a exponentially growing delay on the server's response for requests coming in too quick succession.
I would have set it to only show the captcha if the delay was active, so users would effectively have had a choice of wait or captcha.