You might have too many host entries in fail2ban database:

fail2ban-client status sshd

Status for the jail: sshd
|- Filter
|  |- Currently failed: 12
|  |- Total failed: 240087
|  `- File list:    /var/log/auth.log
`- Actions
   |- Currently banned: 21
   |- Total banned: 27216
   `- Banned IP list: ...

This requires fail2ban minimum version 0.10.0:

fail2ban-client unban --all             unbans all IP addresses (in all jails and database)
fail2ban-client unban <IP> ... <IP>     unbans <IP> (in all jails and database)

A nice trick in older versions is to get the current bantime, then set it to 1, wait for all hosts to be flushed and then revert back to the original bantime:

fail2ban-client get sshd bantime
18000

fail2ban-client set sshd bantime 1

Now watch the syslogs and keep an eye on your iptables. Once everything is gone:

fail2ban-client set sshd bantime 18000

This will always work and it's fast. Let's find the fail2ban database location:

fail2ban-client get dbfile
Current database file is:
`- /var/lib/fail2ban/fail2ban.sqlite3

Great, let's delete it:

systemctl stop fail2ban
rm -f /var/lib/fail2ban/fail2ban.sqlite3
systemctl start fail2ban

A new database will now be created.