Sounds like the answer is to increase the response size for failed login requests. At $12.5/G, if you blow up your response to a mega byte, they'll spend about a cent per try - close to the rate they'll need to pay to have recaptchas solved by humans.