How to set up Catch-all for non-existant users in Postfix

Postfix's Catch-all works well for existing mailboxes, but not for random mailboxes. Sending to a non-existent mailbox gives the following error in the maillog:

Recipient address rejected: User unknown in virtual mailbox table; from=<fake@gmail.com>to=<random@mydomain.tld> proto=ESMTP helo=<mail-oa0-f47.google.com>.

How do I make the Catch-all work for non-existent mailboxes?

Make sure to use the virtual_alias_maps directive in your Postfix main.cf file instead of virtual_mailbox_alias_maps. This will resolve the issue.