I faced similar problem at one of my client's setup.
These mails must be originated from only one or two ids on your server, most probably with generic username/passwd like admin/admin, store/store, administrator/admin etc. You may check mail logs, mail queue etc., and check auth.log also.
After getting the username, check that user's home directory... you may find some malicious scripts and unusual directories into the same. Remove them, or if you are not sure about any directory, you can move them to some another place, where no one has access.
Change passwd for that user, remove mails from differed queue, & you're done.
Hope this helps.