Network Load Balancer sending traffic to terminated hosts

I have a network load balancer with two target groups (http, https). There are six servers in the groups that I had to replace recently, and the setting 'Terminate connections on reregistration' was off. After replacing the servers and deleting the old ones, many of our users were unable to reach our sites anymore, just getting a generic browser 'network unreachable' error. When I turned off stickiness, it seemed to fix it for the most part, but randomly we are still getting network unreachable errors. If I turn on stickiness again, those users are unable to access the servers again. We keep getting notifications that our sites are down from monitoring software when it gets the bad server(s) from the load balancer.

My understanding is there is a cookie in the load balancer, probably matching ip addresses. It seems like somehow these cookies need to be cleared, but I can't find a way to do this.