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 :)