Spammers spamming using our addresses

Vesty writes: "I recently enabled a catchall on our domain while our company transitioned to a new website. I didn't want emails going astray etc while things changed over... Recently I've noticed that on the catchall I get a LOT of 'delivery failure' and similar emails, that are all being returned to the same non active alias. After a bit of digging I discovered that about half a dozen different companies spam has been being sent using an alias at our domain as their from address. I've been slowly attempting to call each of the companies, most are extremely shady, occasionally I get a real person that supposedly knows nothing about it. It seems to me that each of these companies has farmed out there 'advertising' to the same third party that is using our address as their from address. I'm sure this has happened to other people, what can we do to stop it? With the amount of spam these fools send I'm worried that any email from our domain will automatically be treated as spam... Anyone have any suggestions? Are they breaking any laws?"