It’s a simple yet frustrating scenario.

What do you do? Nothing. There’s nothing you can do.
I’ve been seeing an uptick in this scenario recently, and it’s very frustrating, not just for individuals like you, but for those of us who manage mail servers as well.
Why is it happening? In a word: spammers. Let’s look at what they’re up to.
Bounces for email you didn't send
Spam often appears to have come from someone who did not send it. If that’s you, you may get bounce messages when that spam is identified as spam by its recipient or when it is sent to invalid email addresses. There’s nothing to be done, as it was never your doing to begin with.
Why did I get a bounce message?
Bounces for emails you didn’t send are just a form of spam. They’re the result of spammers trying to get people to open the spam and click on the links in the spam message.
Spammers want their email to look like it’s coming from someone the recipient might trust. In other words, they want it to look like it’s coming from you. “From: spoofing” allows them to do exactly that. They write messages appearing to come from your email address and maybe even your name. It’s easy to do; they don’t even need to compromise your account. This From: spoofing has been going on for a long time.
If the email address the spammer sent it to belongs to a real person, they see email that looks like it came from you. They often have no idea who you are and may mark it as spam.
Since spammers are simply blasting email out to huge databases of email addresses, they have no idea whether those addresses are legitimate or not. If they send email to an address that no longer exists, never existed1, or recognizes the message as spam, it bounces automatically.
The email delivery system says, “Hey, I can’t deliver this email; I’m going to return it to the sender.” Because the sender information on the “From:” line looks like it was you, you get the bounce message.
None of this happened on your computer or your account. In fact, it had nothing to do with you other than that your email address appeared in a spammer’s database.
Mail server owners are hurting, too
Imagine you run a mail server, like I run the server that sends mail for askleo.com. Now imagine a spammer sends spam that looks like it comes from one of the email addresses on your server; say, leo@askleo.com.
Some of those emails generate a bounce. Some will be identified as spam. All will negatively impact the email reputation of your domain (in my case, askleo.com).
Your domain’s reputation may suffer so that when you send legitimate email, it’s slightly more likely to be flagged as spam…
…not because of anything you did. There’s little you can do other than ensure you have properly configured your domain.2
Do this
Unfortunately, there’s nothing you can do to stop it.
All you can do is mark the bounce message as spam and let your email program handle it from there.
If random strangers complain you’re sending them spam, you can point them at this article. You weren’t involved. It’s not your fault, and there’s nothing you can do.
However, if several of your friends complain that you’re sending them spam, it might be something more. Take a look at “Someone’s Sending From My Email Address; What Can I Do?” That article includes a couple of quick questions to determine whether other things have happened, such as your account being compromised.
From the sound of your scenario — getting a bounce from someone you have never heard of from an address you never sent email to — the best thing to do is mark it as spam and get on with your life.
Footnotes & References
1: This is often the result of a dictionary-style approach to generating email addresses to send to: tom@somerandomservice.com, dick@somerandomservice.com, harry@somerandomservice.com, and so on — whether or not those accounts actually exist.
2: Meaning that you have SPF, DKIM, and DMARC properly set up for the domain you own and are using to send email. While they do somewhat help preserve your reputation, they’re not perfect.
Thanks, Leo. I immediately changed my email password thinking someone had hijacked it, but your answer seems the best bet. I’m now marking it spam and getting on with my life (as you suggested). 🙂
Won’t it be fruitless at best to mark these emails as spam since actually the emails you are getting are not spam – they are messages from the mail system. Hopefully spam filters wouldn’t have the power to keep you from getting error messages/emails from the mail system, but it seems like a bad idea to mark these legitimate error messages/emails as spam.
I’ve been thinking about this a bit. Whenever a mail transfer agent (MTA) receives email (via ESMTP) it adds a Received-from header with the IP address of the MTA which sent the email. There can be several of these. Why can’t the receiving MTA which bounces the email first do a reverse DNS lookup on the originating IP addresses, and if they don’t match the domain of the purported sender, realize it’s a forgery and not bounce?
Or better yet, bounce it to the originating IP address. It’s either the spammers MTA or an open relay, and well, they deserve it. Am I missing something?
Sadly I don’t believe those headers can be strictly counted on — meaning that you could end up bouncing or whatever legitimate email as a result. (PS you can’t bounce “to” an IP address. You can only bounce to an EMAIL address, and they’re rarely related in spam.)
I too was getting “cannot deliver email” messages to someone I didn’t send anything to and don’t even have in my contacts list. It turned out that in my email account I was allowing “Mail Forwarding”. In there was an email account that was no longer in use. So I must have been unknowingly sending mail to that account for who knows how long. Once that account was no longer valid, I would get the ‘cannot deliver’ notice. I reset the mail forwarding feature to NO and removed the phony email address. I checked my other email accounts and found the same issue in one other account. We are apparently sending copies of our emails to hackers without knowing it. I would suggest that everyone check their Mail Forwarding feature.
I’d add that if you think you have been sending your emails to hackers, you should also change your passwords for the affected accounts.
Absolutely! I did change my passwords.