You're receiving "delivery failure" notifications saying that the message sent from me@mydomain.com couldn't be delivered to someone@somewhere.com... but you never sent a message to someone@somewhere.com???  And you're getting lots of these notifications... saying you sent messages to someoneelse@somewhere.com, anyone@anyplace.com, etc..

What you're experiencing is called email spoofing. And unfortunately, it's all too common. Virus writers and other Internet bad guys will "spoof" the sender/return to address of an email in order to hide the real point of origination, or worse, mislead the recipient into thinking it's from someone it's not... phishing scams use this tactic, for instance sending emails from something like acctmgmt@citibank.com.  Unfortunately, this is completely possible due to innate flaws within the design of Internet based email itself.  It's because each potential "mail handler" on the Internet doesn't validate the sender address before it forwards the mail along.

Think of it this way... the same flaw exists in U.S. mail... I could go to any U.S. Postal Service blue mailbox, and drop a letter in it that is addressed to your neighbor, for instance, but I could put your name and home address as the sender... The Postal Service will deliver it, and your neighbor will think it's from you (although there will be some telltale signs like the postmark... but nothing that will point directly to me). The US postal service does not include a mechanism for validating the sender is who they say they are. And right now, Internet email does not either. There are various efforts under way to address this, but for now, it's not there yet.

So, where is the mail coming form?  Basically, there's a couple possibilities:

1) The mail is actually coming from your PC (or from a PC from one of your other mail users on your domain).
This is possible if your PC is infected with a virus/spyware which is sending mail from your system.  For anyone that has an email address on your domain, their system should be thoroughly scanned for spyware and viruses, in an effort to eliminate these. 

2) Your website.  It's possible someone has hacked your website and is using it's access to your host's mail server(s) by using mail credentials you have embedded in your website code (especially if you have mail functions on your site).  You should perform a complete security review on your website... remove any code that sends mail if not absolutely mission critical... and if it is critical and you need to keep it, then investigate making changes to it:
- first, change the password for any email account it uses to send mail.
- look to see if you can lock down the mail function any better.
- add code to log the mail sent via these functions, so you can review it to see if it's been exploited.

3) A spammer's own SMTP mail server, directly connected to the internet (or his ISP's SMTP system isn't locked down properly... this is common in other parts of the world, Asia, Russia, etc... they are spammer's paradises).  In this scenario, they can send mail specifying any "sender" they want to... and as previously noted, SMTP allows this, because there's no built-in way to validate the sender is who they say they are. 

Indeed, it's not a pretty situation...  and it's all due to this innate flaw in internet email.  There are some standards to address this (like SPF, sender policy framework) which help by providing a mechanism to say only servers A, B, and C are allowed to send mail for mail domain). But these only work if both the sender and reciever's ISPs use it, currently they are not widely adopted.

Your best bet is to track down the source...

As noted, if it's a virus/spyware on your system (or the system of any of your mail users) or an exploit on your website, you need to find it and remove it.  If it's someone spamming from their own systems using your domain name, you need to track down a copy of one of those mails, and review the header to find the IP(s) used in transmitting the message (although headers can be forged... ugh!) and then contact the ISP's that own those IPs, and lodge an abuse complaint (and then hope they action it).   Tracking these types of issues down is beyond the scope of services for most hosting providers, including us.  Other than providing this information about the nature of the problem, the scope of our services does not include finding, identifying, or otherwise addressing the source of spoofing issues.

You can HELP protect against this by enabling an SPF record for your domain.  SPF puts a special DNS record in your DNS info that says "mail for my domain should only come from these servers: (list of servers)... this can HELP, but unfortunately, not every ISP checks for SPF records on inbound mail, it's just not widely adopted yet, even though it would virtually stop spoofing overnight.  If you want to create an SPF record for your domain, you can do so through the DNS icon for your domain in your control panel... if you're not familiar with how to do this, no problem, just submit a support request asking for assistance in setting up an SPF record for your domain, and we'll help you define the correct record, and get it implemented in your DNS settings in your control panel.

Of course, if you're not 100% committed to your domain name (I'm sure Coca-Cola's pretty commited to coke.com, but you might not have such an attachment to your domain name)... then it might be way easier for you (though slightly more drastic) to simply change to another domain name... domain registration is very affordable, and you may not wish to expend the same resources to protect your domain name that Coca-Cola expends protecting theirs.