D'oh! suposição ruim da minha parte. Eu dei uma olhada de perto. O fail2ban não bloqueia o IP local, está bloqueando a fonte corretamente. Não é necessário configurar vários endereços IP.
A questão parece ser que eles estavam fazendo dezenas de tentativas por segundo.
2012-07-26 10:41:25,771 fail2ban.actions: WARNING [dovecot-pop3imap] Ban 74.63.241.177
2012-07-26 10:41:27,825 fail2ban.actions: WARNING [dovecot-pop3imap] 74.63.241.177 already banned
2012-07-26 10:41:28,827 fail2ban.actions: WARNING [dovecot-pop3imap] 74.63.241.177 already banned
2012-07-26 10:41:30,829 fail2ban.actions: WARNING [dovecot-pop3imap] 74.63.241.177 already banned
Foi o suficiente para aumentar a contagem de processos antes que o fail2ban pudesse responder. O volume do ataque e a disseminação por vários IPs me pegaram desprevenido.