Publication of results to follow.
Update: Randy thinks this is too harsh and got me in contact with the Yahoo folks. What I said to Yahoo:
We're actually not quite sure if Yahoo's mail servers "suck" or if they're just really aggresive in their anti-spam efforts.From my perspective, Yahoo is the only big email provider whose email servers don't answer somewhat immediately, and my logs are filled with errors that we couldn't establish a connection to *any* of their MX servers in a reasonable amount of time, so mail to Yahoo users had to be delayed until a future attempt.
The success rate of a TCP connect to any of the IPs in the first 3 mx records happening within any sane amount of time is relatively low, compared to other mail servers on the Internet. Sometimes an IP will take a connection in milliseconds, followed by 15 - 120+ seconds the next time (on the same IP), followed by milliseconds again. So it doesn't /seem/ like anti-spam or rate limiting, but instead like poor load balancing.
Or maybe this is intentional and we need to get onto a bulk sender whitelist? I have no clue how your incoming mail servers are setup, though.
If Yahoo wants to greylist me or even tell me "4xx too busy try later" immediately upon connect (which they do, sometimes), I'm fine with that. But not even taking a connection for 12+ seconds is just ridiculous. I send email to gmail and it's taken in milliseconds and is server-pushed to the gmail client in the browser within a second after that. That's just impressive. Not so impressed with Yahoo's end-to-end.