Another commenter mentions ProtonMail, but somewhat unadvertised is with a paid Proton sub (I forget which tier), you also get access to SimpleLogin. It's a service which lets you create new email aliases with your domain that just send them to another email you own. (Also lets you send emails as that alias, so the other end doesn't see your real address.)
I use it with Vault/Bitwarden, which lets me generate email addresses of format `<uuid>@my.domain.com` when I create new login info for services.
The problem with catch-all inbox is when you have to reply to an email. Then you have to create the email address to be able to send emails from it. Or are there other solutions?
When you reply, any sensible system will use the address you received it at. Fastmail does this, as do many others (I used Thunderbird for many years, possibly with an extension to do that). To send an email from scratch you just type the address you want in the from field or select from a list. At no point is there any need to create specific addresses, as the catch-all means all addresses are already valid.
I misphrased my query; I already run my own mail server and am using a unique e-mail address for every service. I'm wondering if there's a provider with a common domain name shared between lots of users that still allows such a large number of aliases. That would let me use a fake name for anything that doesn't need my real identity, and wouldn't reveal my identity in the case of a breach. Has any e-mail provider found a way to implement this while preventing abuse?
I'm using my own domain right now, but that can only uncover who has leaked my data; does not provide additional privacy.