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.

can you help ?   pmta yahoo  is send 2000 in       out: 0      is err TSS04 

Still working on it pixaga7651 ... will post when I know we have a solution, don't want lots of extraneous "fluff" before then.

ok thank's bro 

Follow up...

AOL.com delivery has cleared up on their own (must be some sort of timed blockage).

Yahoo.com however continues to block us.  Is impacting more and more clients now.

(Updated)

Yahoo is also now accepting our inbound messages, they are however delivering them to their users SPAM folder instead of the inbox.  But at least they are getting there.

I think this just ended up resolving itself after being essentially IDS'd for X amount of time.  Seeing it started last Monday, looks like a full week.

We never did find any way to communicate with any knowledgeable Yahoo nor AOL tech support staff.

We did fill out a form that apparently provides to users receiving email from us a link to OPT-OUT (inserted by Yahoo).  And yet the email I received did not have that link in it.

So who knows.   What a mess.

I've been having this problem also.  They have blocked at least 2 Class Cs of ours as all 6 IPs bound to our mail server cannot get through and only 1 of them was in use when they started blocking us and I tried another block of IP's that has never been used on a different Class C and that too failed.  We have SPF set up for the vast majority of our clients and DKIM in many cases also.  We have not had a hijacked account in many months and we place strict limits on email volume from individual accounts in order to prevent our mail server being used for bulk email.  It is likely they blocked us based on forwarded email that was spam, though we filter out the vast majority of it and we don't have many accounts forwarding, especially to AOL and Yahoo.

I tried their feedback loop which is what the OP tried, but that did nothing to resolve the issue, plus you have to set it up for every single domain.  Postmaster support refused to escallate and gave the most insane non-answers possible in their replies.  It appears 100% useless to contact their postmaster support.

I don't know what to do as all of our owned IP space is blocked.  This could end up being extremely costly for me from loss of business.  My only possible remedy is to set up an outbound gateway somewhere else.

After filing the form with yahoo, it took a full week before things cleared up.

So far so good, no further issues.