The dark side of catch all

I use my own domain for email service which uses Google Apps For Your Domain. I had almost 0% spam in my mailbox. For this I used variety of approaches like:

1. Mailinator: I've been using Mailinator from a very long time for signing up for any non important website. After webmaster became aware of popularity of mailinator they began blocking Mailinator and its affiliated domain for signup. After that I setup my own mx record to work with Mailinator . You can also use anything@extra.roshankarki.com.np and check your email at anything.mailinator.com . If you haven't realized yet anything, can be literally anything. The only problem with this method is you can't use this with more personal website.
2. The + trick: The beauty of Gmail is that you can add anything in your email address username part by adding +. So whenever you've to signup for websites you can use email address like username+newwebsite@gmail.com . If you start receiving spam on  this email address you can easily create filter to get rid of this. The problem with this is it won't be long before spammers will strip + part and start spamming you. After all this will only take one line of code to do so.
3. Bugmenot.com: If I've to register in some website I check this site before doing so. This website has username and password for many sites so that you don't have to register one yourself. You can also add your own and vote on whether listed ones worked or not. The problem with this is not every website is listed here.
4. Third party email filtering service: There are third party websites that will act as a firewall for your incoming email. Anyone sending you email will get another email, which will have a link, which until clicked won't deliver his/her email to you. While this idea sounds nice, this won't work with legitimate auto mailing software and I might actually miss important email if someone doesn't understand or doesn't want to go through the trouble.

So my best bet that had worked for me all these five years was Catch All.

What this basically is, you can forward emails sent to any email address that doesn't exist in your domain to another email address. For example if someone sends an email to userNonExisting@domain.com instead of bouncing back it can be forwarded to cathAllEmail@domain.com . This is like the + trick but in more advanced form. So with this method I could give personalized email address to all and still get email at my main inbox. If I had to sign up for ABC food delivery website I'd give the personalized email address abcfooddelivery@mydomain.com .

I have created one generic spam email address. If any personalized email address starts sending spam I add that email address as nick name to this generic spam email address.

Now the problem:

Spammers uses random domain name to send spam. And unfortunately they chose me. What happens with this is they generate random username at my domain . So if the email bounces back, due to catch all the email lands on my mail box. I can't create filter because they use random user name. The solution that I've applied are SPF and DKIM which has reduced this spam. So these days there are spams in my mailbox :(