Bug#1022578: fail2ban: Exim beeing attacked, but fail2ban refuses to block because "Too many errors"...
I'm seeing the same issue, and on my system it consistently coincides with the Exim log file being rotated. This means that fail2ban will work until the end of the day and then needs to be restarted.
Bug#990414: Related issue
As a side note, the output triggering this issue is described in bug 474349: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=474349