Yahoo have always had rate limits and cumulative counters and in every company where I managed outbound mail servers from data-centers I had to set up separate queues and destination limits for their domain or I would get the same effect you are seeing. It does not show up right away. They have always had some of the strictest rate limit policies.
The only remedy I know of is to set up queues and rate limits specific to their domain and setting gradual back-off timers. Distributing the queue into multiple outbound servers or data-centers will not work if using the same sending domain.
I am assuming you have configured SPF, DKIM, and a published DMARC policy and have checked your reputation in their sender hub [1][2] and have warmed up your IP addresses reputation (as you have it in their error message).