To try to answer my own question, I suppose they could try detecting elevated login rates. Let's do the math:

Getting a few thousand IP addresses for a month is cost-effective for any serious business (criminal or otherwise, but especially criminals that can buy botnet access). Spreading it out over a month, you could do 0.1 logins per minute to stay under the radar and get:

0.1 × 60 minutes × 24 hours × 30.4 days/month × 1000 IP addresses = 4.4 million login attempts

> The [attackers logged in] to around 14,000 accounts using previously compromised login credentials

14k is well below 4.4M. To get that number lower than 14k (assuming they only ever use 1000 IPs), you need to ensure each IP address stays below 0.07 logins per day. Even allowing some bursting (3 attempts on some of the days), that's going to block paying customers from logging in.