For this type issues,
1. We need to first check IP is listed on blacklist.
2. Then check our side that there is any possibility of open relay(anomalous MTA)
3. Need to check is there any chance of compromise user accounts(you can check this by daily mail report which has received to admin mailbox..)
4. If every thing is fine..
then you need to apply for IP release (Removal Procedure) by sending email to Spamhaus from respective mail server.
IP release procedure:
Spamhaus Removal Procedure URL syntax: http://www.spamhaus.org/query/bl?ip=<your IP>
If your IP is listed on blacklist then it will give you the SBL id..
Edit below URL with your your SBL ID (<ID>)
For E.g. : SBL - The Spamhaus Project
access the URL and under "Removal Procedure" you need to send mail to SPAMHAUS by clicking on "use this link" (if you PC has the mail client then it will automatically open)
That's it.. send mail with detailed issue and wait for Spamhaus people respond, if every thing fine then they will release IP with in couple of days.. :)