Mail problems...why?

We had a few paid email accounts that were used for spam. We investigated and shut it down once we became aware of it but now we have to clean up the resulting mess. We are working on remote providers like gmail now, as we become aware of them, but remote providers often knee-jerk to add hosts to a block list, and take their time to remove them.