Our clients site got infected and was blacklisted. We spent weeks fixing and clearing up the site and got it completely removed from all lists. The site is now squeaky clean as of a few weeks ago but the clients emails are still bouncing due to them being marked as spam. Could the fact they manage their emails on a separate service have anything to do with this?
Your situation is not entirely clear because I do not have the information to let you know specifically what is happening. But here is what I know.
Blacklists can list domain name and/or IP address depending upon the blacklist. IP addresses are preferred by blacklists in general. Likely, your domain name was reversed at the least and the IP address blacklisted.
Some blacklists take as much as a year to drop an entry while others drop in weeks or even days. Some offer options to clear your entry from their list using their website and others do not. Some rejection e-mails may tell you what blacklist your site was found on. If you do not have a clue, use the website mentioned earlier and go to the blacklist website and see if you can request to have your entry dropped. Often you can just use the same blacklist domain name (with sub-domain) to get to a website or use the parent domain. Some blacklists do not offer a website.
Some SMTP anti-spam services use 1 or 2 harsher lists. I dropped the more harsh lists from my filters and many companies do too. But companies like AT&T do not. Some cache any entry in their own blacklist to reduce traffic. Google uses black lists for both e-mail and web stuff. One customer was blocked from Google for a while because of blacklists. Depending upon where you are sending e-mail, even after you are cleared, it may be that some SMTP servers will still reject your e-mail for a period. I dealt with this a while ago for a customer. While the entry was dropped almost immediately upon request, it took about a year for a few services to stop blocking e-mail. That was heart breaking because my customer did not send spam, but someone on the net block did.
It would be nice if blacklists and anti-spam efforts were more dynamic and precise. This could happen but it is up to the blacklist operators and SMTP admins to decide what they want to do fair or unfair.