I'm currently working on reducing the risk of mass account lockout on a site that (unfortunately) issues sequential, numeric user IDs. Changing the structure of the userID is not an option at this point.
I've looked at a few options (CAPTCHA, Restrictions on login attempts per IP). One think I am thinking about is the use of an anti-CSRF token on the login page, requiring an attacker to load the login page (and get the token) prior to any login attempt. This would probably be combined with a delay before the token would be accepted (several seconds, the time taken for a regular user to enter login details).
This would not prevent lockout, but it would slow down the rate of attempts, and slightly increase the complexity of performing the lockout. Has anyone seen this used before? Would it really work?