I made all kinds of good faith efforts personally to contact someone at AT&T through their forms and phone numbers, without ever even speaking to anyone who could resolve the problem if they wanted to. Lacking any other way to get through to them, legal seemed like the only recourse.

I would think that if you were the ISP owner blocking our mail to your customer, a single phone call from the customer or from us would convince you that our IPs were not a spam threat. That's certainly the way I prefer to deal with anything. But when dealing with something as monolithic and totally deaf as AT&T, lawyers were the only way.