After running fail2ban in debug mode and investigating IP tables I have found the problem.
The problem occurs because of 3 reasons:
1) HAProxy is running a docker image with server time in UTC and your servers might be in a different time zone.
2) HAProxy is running in a docker container in a Cattle managed network which means that the incoming packets are Forward packets and not Input packets for iptables.
3) The way Cattle handles forwarding is a bit ugly and hence does not allow custom fail2ban rules
In my case as HAProxy is in a docker image with a different timezone, fail2ban was ignoring ban attempts as the time was a few hours off. Changing the server time fixed the first problem.
I could now see that IPs were indeed being banned when using:
fail2ban-client status <my-jail>
But the problem still remained cause even though I could see the correct IPs being banned, I could still access the server completely fine.
This is because of the way Rancher sets up iptables. To fix this problem I changed my /etc/fail2ban/jail.local from:
[DEFAULT]
...
chain = INPUT
...
To:
[DEFAULT]
...
chain = CATTLE_FORWARD
...
Now the users are correctly banned because the timezone matches and are then put into a jail in the Forward chain hence dropping requests from banned users.