If your server was used as a "relay" for people spamming others. One of the ways other admins will react will be to filter out your domain. Or your domain may be on a Blacklisting server.
"Blacklisting" blocks delivery of ALL mail from sites that allow open relaying. This is done by using "Real Time Black Holes" (RTBH), databases that list sites known to deliver spam, whether they meant to or not. Sites that want to eliminate spam can set their mailservers to query these databases to determine if the source site is a "known spam site", and reject any mail from servers on the list. One of the primary criteria for being listed in RTBH is having an open relay -- it doesn't matter if any spam is actually being sent through your open relay, RTBH databases will blacklist you because spammers could send spam through your open relay.
See if you can relay through your servers. Correct it. And have blacklisting sites test and remove your domain once the problem is resolved.