The solution we employed was a "dumb" fail2ban like script to ban any abusive IP address. It worked wonders and practically completely neutralized the attacks. We received zero complaints from any legitimate users of the service.
If I recall correctly, even after the attacks subsided (CVEs was patched etc.), we still kept a toned down version of the script in place.
> at best, fail2ban: does nothing
This is just plain wrong. Even if you're only using key based auth and there's no way an attacker could have your keys, fail2ban will still block the abusive traffic.
I have no issues with blocking abusive traffic instead of letting the attackers beat their fists against my armored doors.
> at worst, fail2ban: causes you massive inconvinience or total lockout
The authors main criticism seem to be that you might lock yourself out of your own server one day. This hardly seems fair because the author is saying "just setup SSH correctly and you won't have any issues" while also saying "if you don't setup fail2ban correctly, you'll have a whole bunch of issues!" OK, so shouldn't we just setup fail2ban correctly as well?
Having said all that, my recommendation for people who are going to use an indiscriminate fail2ban setup on SSH access would be to have some out-of-band access in case you do happen to ban yourself, even if it's less convenient to use than SSH.