Any suggestions on which provider to use?

IMO, it depends on how many mailboxes and aliases you need. Providers like Fastmail charge by the mailbox (with up to 600 aliases for each). Same with Runbox, Mailbox.org, etc. (the number of aliases varies). Migadu provides unlimited domains, mailboxes and aliases for a fixed price that decides how many outgoing mails you can send everyday from all mailboxes in that account.

I use FastMail like this. They support both catch-all ([email protected]) and user-specific forwards ([email protected] -> [email protected]) for domains with multiple users.

As the people above mentioned, look for one that supports a catch-all address. It makes it very easy to manage. You can even respond using a real "DoNotReply" account and the alias as the "replyto" address for the rare occasions you do want to reply. Yes, Google Apps does this well, but there must be others.

Google Apps works great for this. You can also setup a catch-all account and not need to pre-configure the aliases in advance.