You're a victim of what the spyware / spam community calls a joe job, a deliberate effort to send out spam or other email (often viruses or spyware) masquerading as part of your domain or even as you, rather than having the sender be their own account.

Unfortunately, there's really not much you can do about this sort of problem, though it's definitely important to check and ensure that you don't have an open mail relay or otherwise aren't actually hosting the spam messages being sent out: if your system is compromised, spam being sent might be the least of your problems!

Here's information on how to test for an open relay: quick check for an open mail relay.

If you do find that your site is open or, upon investigation, has been hacked, then I suggest the following sequence of events (and yes, they're painful):

1. Pull your server off the net completely.
2. Do a full backup
3. Reinstall the operating system and all important software (including Web server, common CGI scripts, the SQL database system, etc).
4. Check your FTP archives to ensure that you aren't inadvertently hosting any porn or warez.
5. Get help so you can identify how they came in (was it a bad password, a social engineering hack, a known exploit you didn't patch, a poorly written script, or what?) and fix it.
6. Come back online and carefully monitor attempts to connect to your telnet, ssh and ftp ports.

If you're clean, you're not an open relay and your system hasn't been compromised, then all you can do when you're the victim of a "joe job" is to just wait it out and apologize (and explain) if you get any grumbly email from victims. You can point them to the following Wikipedia page to explain what's happening:

    http://en.wikipedia.org/wiki/Joe_job

Good luck! This is a very frustrating experience, I know.