Yes. And that’s the thing I hate most about setting up new servers. Some of the blocklists can be a nightmare to get off. Microsoft and Verizon, for example, are completely unhelpful.
My tactic with Microsoft is to wait until I get the first boilerplate denial. Then I copy it back to them, substituting their own IP range. I actually block the entire range, and inform them that they are not eligible for remediation because of excessive spam coming from their servers. (Microsoft servers do in fact account for 35 - 45 percent of my incoming spam.) That gets my request escalated and the block removed. It’s worked every time.
Verizon is trickier because I don’t think humans ever read the requests. But the last time I was in that situation, I found that submitting a request to AT&T or SBC Global got the Verizon block removed. I guess they all use the same list.
SORBS is strange. Sometimes they immediately remove the block and sometimes they take weeks. They do tend to respond more quickly to requests made by the DC, so I usually let them do it for me.
The rest are pretty easy. Most of them are self-rehabilitating and have already cleared by the time the IP is reissued.