Too late to edit my original post, but I want to address a few questions that were brought up by several people.

1. I don't know how the lawyers worded the letters. Obviously it's not illegal for a host to block inbound mail. But clearly the legal team made someone look more closely at our particular case. If you're not doing anything nefarious, it's easy for someone mid-level to clear you off a blacklist if they want to. The company I work for isn't a household name outside a few states, but it's large and respectable enough that getting a cursory glance from someone with the power to say "take them off the blacklist" is probably enough.

2. We've had these IPs for > 5 years. Our reverse DNS, DKIM, SPF are all in order. The mail comes from the same IPs as the company's main website/app services. The company uses Constant Contact for marketing emails, so our outbound server only sends things like receipts for purchases, service agreements, confirmations of renewal/cancellation, verification codes for login (password reset / new signup / new device), and intra-company mail which sometimes goes to employees' personal addresses. Being able to firmly state that we never send marketing off this server, and we regularly assess exim logs and we are sure we've never been hijacked has usually gotten good results, even without lawyers.

3. When we first got these IPs, around 2015, there were more problems. I don't know who they belonged to before. For the first year it was whack-a-mole with the blacklists. But truthfully, I've never had a problem personally getting us taken off any of the public blacklists shown on mxtoolbox. It's the private blacklists of mail providers like AT&T, Comcast and AOL that caused repeated issues. There's no public way to check if you're on these, and as far as I can tell their removal forms are black holes. The removal form for AT&T looks like it hasn't been updated since the '90s, and I've never received even an automated response from using it.

4. We did, for awhile, advise customers to get other email addresses. Unfortunately, the customers with an @comcast or @att account are also probably the least tech-savvy. It's just not feasible to have customers calling their local retail outlet and having a manager spend an hour trying to walk them through why they didn't get their signup verification code, and three days later this bubbles up to corporate and finally to me. And it isn't a good look for us as a company to say "sorry, Comcast doesn't like us for some reason."

5. For awhile we had customers write to Comcast and AT&T asking why they were bouncing important emails from us. Overall this had basically no effect. The customers would get back automated emails telling them how to configure Outlook. However, one such customer was a lawyer who I ended up corresponding with personally (through my gmail account, since he couldn't get my emails), who got such a bug up his butt about it that he seemed to get AT&T to unblock us, which only lasted a month or so. This was where I got the idea to approach the CEO about unleashing the legal department.

6. Variations of "Don't waste $500/hr. on a lawyer". IMHO lawyers are pretty terrible to have against you, and pretty awesome to have on your side. I'm glad I work for a company whose philosophy is to keep as much of our infrastructure as possible in-house, and which also refuses to pony up something that feels like a ransom, even if it would be more expedient. I personally don't have $500/hr. to pay a lawyer, and it would be a much worse uphill battle for a sole proprietor or small company these days trying to manage their own email server than it was ten years ago, or is now even with the backing of a larger company. But it's important to us that we don't get pushed around by big providers, and retain as much autonomy as possible in our business dealings with customers. That's part of the philosophy I brought to the company, it's why we run dedicated hardware, and I'm the one who pushed to spend the money to have the lawyers get involved. If more mid-sized companies took this approach, and if other IT leads pushed for running their own metal and their own mailservers (granted, yeah, it's an endless pain in the ass), then big email providers would be forced to actually take things on a case by case basis the way they did ten years ago, rather than block blacklisting whole /24s with the assumption that every company and individual will eventually cave and be forced into their monopoly. So to whoever says that decline is inevitable, save your money, lawyers suck, etc, without offering any positive solutions: you're welcome.