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.
Most criminals are not using services like Luminati - they are using actual botnets made up of compromised computers. In that case, their bandwidth costs are far cheaper than yours.
I don't know how expensive it is with Google/AWS, but I'm paying about $1.50 per TB at my non-cloud-host (vs their $12500/TB), so if it comes down to it, they need to outspend me by multiple magnitudes. Sucks, but still cheaper than losing customers due to hyper-annoying Recaptchas, and I doubt that somebody is willing to stomach $12500 cost to make me suffer $1.50 ... I'm sure there would be more efficient attacks ;)
