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.