@jbhowlesr:
I would suggest that if you send a request to be delisted from the blocked list, that you include some data about your network to include any finding of infected machine, hijacks etc and exactly what you did to fix the problem and steps taken to ensure it doesn't happen again. Typically when providing this level of detail, companies who list spam offenders will give extra consideration since you put in the effort on your end to solve any issue. Considering working with them to get off the list. Otherwise, if you only ask to be removed with as little or few words as possible; your request will sound less than genuine.
The problem in this case has nothing to with sending spam. The blacklist in question is for sites with botched MX records that fail to for example to provide A records for hosts listed in the MX records for the domain.