Резюме:
Может кому ещё пригодится. Способов усложнить жизнь брутфорсерам, много. Мне показалось, самый простой способ, сделать так:
apt-get install sshutout
service sshutout start
Всё, можно проверять. Алгоритм для такого рода прог, стандартный, смотрит в /var/log/messages и банет в iptables на прописанное в /etc/sshutout.conf количество секунд.
Для дяди Миши: Почитал про -m state --state, забавное решение, но наверное я не буду свои каракули городить, отсылаю любопытствующих к хорошему источнику
http://ru.wikipedia.org/wiki/Iptables Там несколько примеров блокировки :22 через iptables, а кроме того, любопытный метод "стука" и другие полноценные примеры.
Спасибо всем ответившим!
Кстати, если чего не так, поправьте.