I've been using my own domain with a catchall for over 10 years and never had problems with spam. Spammers tend to send to harvested address lists, not just try to send to random mailboxes for a domain.
The solution is probably to tell the senders that they're effectively sending out spam / doing a variant of open relaying by emailing the spoofed address, but even internet-savvy institutions like an IP address assigning organization (RIPE) sends me backscatter so I don't have a ton of hope