I have worked through all the Blacklists that were logged, requesting de-listing for our mail server.  There are a couple where no mechanism exists to request a de-list, it’s automatic and time based.

There are also some mail sitting in queue because the destination server thinks we are still blacklisted because of the way real time black hole lists work.  These lists use DNS to distribute status information for each IP.  DNS is cached, and so even when an RBL de-lists our server, a site that our server tried to deliver to while we were listed still sees us as listed until the time to live (TTL) expires for the DNS zone in question.

At this point, our server is fixed and better secured and I’ve contacted every RBL that has a manual list method.