limiting ssh login attempts by ip

[csnyder]

I've noticed a marked increase in dictionary attacks against sshd
lately -- tens or even hundreds of connection attempts from the same
IP address within a short timespan.

I wrote a script that creates firewall rules to drop packets from IPs
with more than n login failures over the last 10 minutes, but it's a
half-measure -- in the minute it takes for cron to get to it, an
attacking script can try a lot of different passwords, even with
MaxStartups set low.

How do you protect your servers from this kind of attack? Especially
on where you can't enforce a strict password policy or make everyone
use keys?