Today I have sent multiple messages from my Zoho Mail account and they have failed to arrive at a recipient using MS Exchange Online (not even into Junk) although they show as delivered in Zoho's logs.

I called in some favours with that recipient and had them look through their logs. The messages are being quarantined as they are being given a Bulk Complaint Level of 9 (very high). My SPF/DKIM records are all good and my domain isn't on any blacklists according to MX Toolbox. Have the Zoho SMTP servers been used for spam a lot lately and gotten a bad reputation?