I am not sure what exactly the problem is here, but let's work through some of the options. Is all the mail you are sending being marked as spam by receivers, and hence your user's mail is not going through? If so, there are a few things you need to ascertain and fix. Find out why the email is being marked as spam -- most likely your IP address range was used by a spammer in the past and has been added to one or more spam blacklists. If this is so, you'll need to contact the blacklists to remove your IP addresses from the list.
If the email being generated is spam from (or through) your mail server or your hosts, then you could be in one of two situations -- either your host is an open relay or one of your hosts has been compromised and is being used to disseminate spam. In the first instance, an open relay is a mail server that allows anyone on the Internet to send mail through it. Check your mail server's logs to confirm this. You can also test if your mail servers are an open relay by using tools like mail relay testing or the SMTP open relay test. If you are an open relay, then you'll need to consult your mail server's documentation to determine how to change this.
In the second instance, you'll need to review your mail server's logs to determine which of your hosts has been compromised. Then, shut down that host or hosts and follow your standard incident or forensic processes to determine how the compromise occurs and what you need to do to fix those hosts. If you don't feel confident to do this yourself you may want to consider engaging a third-party IT security consultancy or organization.
By the way, If one of your hosts has been compromised, you might find that you have also been added to some spam blacklists. You'll need to check and confirm this and then work with the blacklists to remove yourself. Be mindful that dealing with some of these blacklists can be complicated and time-consuming.
This was first published in May 2007