Sometimes you have to tweak the default fail2ban frequency downward in order to keep it working. Must be some of the script kiddies are unleashing bots that are aware of the default rate fail2ban ships with.

I've seen the poor server spitting out "password incorrect" messages perpetually, despite fail2ban running. Just enough of a pause to avoid triggering the target.