You are correct, the problem started only after placing new Arista border routers. The previous border routers were not doing ECMP. The issue was a combination

You are correct, the problem started only after placing new Arista border routers. The previous border routers were not doing ECMP. The issue was a combination of the use of anycast, diverse Internet transit egress, this model of Arista defaulting to using the packet's TTL in its ECMP hash calculations, and the end-customer router CPE egressing packets that are part of the same TCP connection with variable TTL values. Change any one of those items and the issue would not have shown up.