How many clients are connected to the relays in total that the other clients are not getting connected to like they should?
It could be that the maximum clients per relay threshold is being hit for that relay, which would be why they are getting bounced.
It may also be possible that the maximum number of open / half-open TCP connections limit is being hit for the OS of the relay itself. This may need to be adjusted.