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.

It took quite a lot of knowledge what blacklists are out there and time to check them all. It's hardly "just a few minutes to write an e-mail".

https://mxtoolbox.com/blacklists.aspx takes a few seconds? Then to follow up is a few more minutes

There have been sites that check an IP against the vast majority of blacklists for well over a decade, and they've been free as well.

https://encrypted.google.com/search?hl=en&q=how%20to%20check...

I run RBL checks a few times a day in Nagios, so I don't get surprised.

I used http://multirbl.valli.org/ but who knows how many are out there, not including private lists.

It's the private lists that will get you. What do you do if Google has your IP address on an internal blacklist? Or your health insurance company? Or some random Barracuda-style e-mail filtering appliance? Nothing. You're screwed.

In that case, the IP is screwed. I plan change IP, or hop hosts if/when this happens. I opened 6 accounts on 6 different hosts, and only two are active for this reasons. So far so good :)