Out in the big world there are alot of different blacklists to use with your e-mail flow, and among them there are some more aggressive then other. Some follow a best practice way of blacklisting, and some doesn’t.
Office 365 are using a pool of public IPs, so this will not regard every customer or every day for the same customer.
Blacklists as SpamCannibal are blacklisting IPs instead of sender domain.
As this is not how the majority of blacklists would have done it, Microsoft will not use resources to get whitelistet at these companies.
In some level I can agree to this, because the way they blacklist IP addresses is wrong. Sadly this doesn’t end over the night and becomes a problem for Office 365 customers.
The solution for now is to ask the recipient IT Administrator to whitelist your domain or better all of Microsoft Office 365 public IPs.
For Hybrid Customers you can reconfigure your Hybrid so all outbound e-mail from Office 365 users go trough your On-Premise Exchange Servers and therefore doesn’t send with one of Microsofts public IPs.
This will aslo affect customers only using Exchange Online Protection for outbound spamfilter.