I'd add to Ted's thoughts that managing and navigating the blacklists is part and parcel of a (real) mail admin's job. It's relatively easy to have addresses removed the first few times, so I'd say, get your ducks in a row, find a reliable blacklist monitoring service, and roll your own.
I used to be in the ISP business. I sold that, and now I have an IT services company. We host mail as part of our IT business, and I can tell you that for the 100 or so zones we manage, I spend about 3 to 5 hours a week on blacklist and delivery related issues. It's just the way it works. Spam detection/prevention is five percent science, five percent skill, and 90 percent FM. You'll find most of the large providers (AOL, AT&T, Yahoo) are extremely hard to work with. Gmail, on the other hand, is incredibly easy to work with. Just my $0.02. Tom
