SPF??

Our SPF, DMARC and DKIM have all been confirmed active and correct.

Good thought though! 

Was first place I checked.

That's why wondering if it is a more global thing than just my server.

Not seeing us black-listed anywhere either.

Finally got a bounce response from them... looks like they themselves have us blocked... sigh...

The error message is not related to SPF or DMARC; it is a temporary block that occasionally applies to AOL/Yahoo.

It is necessary to send a form to Yahoo's Postmaster; the problem is that they take too long to respond. In my case, I have had similar blocks; they unblocked the IP in two instances, and with another IP, they advised me that the best option was to change the email server's IP.

Go through your users and see who is automatically forwarding email to AOL and yahoo. They forward email to themselves and it ends up being spam, and then they report the spam and get their own servers blocked

We're seeing something similar with Yahoo and Gmail, but without the rejection.  The emails are being accepted for delivery, but are dropped into the recipient's Junk folder, even for emails that are replies to messages originated by those same Gmail and Yahoo subscribers.  Initial emails are are squeaky clean and legit, content-wise, also.

We manually verified SPF, DKIM and DMARC are spot-on.  Then we used MX Toolbox's various checkers to have a machine verify everything checks out.  We ran multirbl.valli on our IP address space, and none are listed in any RBL, and the SenderBase score for all IPs used for email is "good".

We can easily deliver to any other service with zero problem, but Yahoo and Gmail are "junk"ing a significant percentage.
 

I suggest you use Gmail's Postmaster Tools platform; there you can find the reasons why emails are being blocked, sent to spam, IP quality, among other factors.

We use it frequently; it's very helpful and has assisted us in resolving issues with our users.

Thanks for all the recommendations, we are following up with Yahoo, they are having us add a TXT record in our Primary domains DNS for which they can then setup an "allow" rules of some sort I guess.

Will post back here if that fixes it or not, and any other information on exactly what had to be done for "future generations" to review once resolved.