I had this sort of thing happen yesterday. Two IP addresses in my email server's /24 were flagged for spam so the whole range was blacklisted. I wasn't able to send email for about 8 hours until it was cleared for me. But this was 8 hours of outgoing email downtime in two years of running my own server.