Вот что творят, гады:

$ grep -c "Address does not exist" /var/log/exim/rejectlog
149908
$ zgrep -c "Address does not exist" /var/log/exim/rejectlog.0.gz
345280


Может, посоветуете какую утилиту для бана негодяев?

Пока ничего, окромя собственного скрипта, в голову не приходит - поиск в гугле находит банилку только под ssh