Is rate limiting by IP the best way to handle something like this (other than the obvious, allowing better passwords)? You could obviously rate limit by account, but then you make it easy for anyone to lock anyone else out of their account. And obviously rate limiting by cookies as mentioned is awful.

There's no great way to "handle" something like this besides modifying the protocol to be less vulnerable.