My former iptables ruleset was wrong.
This seems to work better:
# SSH brute force protection $EXT_IF
$IPTABLES -N ssh_brute
$IPTABLES -A INPUT -i $EXT_IF -p tcp --dport 22 -m state --state NEW \
-j ssh_brute
$IPTABLES -A ssh_brute -m recent --set
$IPTABLES -A ssh_brute -m recent ! --rcheck --seconds 300 --hitcount \
4 -j RETURN
$IPTABLES -A ssh_brute -m limit -j LOG --log-prefix "ssh_bruteforce "
$IPTABLES -A ssh_brute -j DROP