After doing a bit of digging, it doesn't appear the any of the ip-space is blacklisted (one less battle I have to fight). Fortune 100? Nope. Just a small non-profit org in Tacoma, WA, that got their exchange box rooted. I'm still trying to figure out the full extent of the damage done, but this point, I believe 99.7% of the outbound mail is legit. In-bound is another story entirely, but that's my own private hell to deal with.
Thanks all for the input

This in no way is a negative assumption on your skills. There is
some important information missing from the above details. You wrote
that your Exchange box was rooted, but you didn't indicate what you
did to resolve that. I'm not looking for the details of what you did,
just an overall statement about how you rectified it. You also
indicate that you are still assessing the full extent of the damage,
is that to the Exchange box or to the IP space?


-Jim P.

Can you please take this to a mailing list which cares about mail servers? I can think of nearly 50 without trying. Thanks.