Make sure all domains are set to Internal Relay, not Authoritative. ALL DOMAINS MUST BE SET TO THIS, otherwise none of this will work.
Do this from Mail Flow>Accepted Domains
Create a shared mailbox for the catchall messages to go to and set yourself as an admin. If you don't want to deal with a separate mailbox, you can set mail here to be forwarded to you.
Do this from Recipients>Shared.
Create a dynamic distribution list that will contain all valid users.
Do this from Recipients>Groups
Create a rule to send mail to the catchall mailbox if it is not sent to a valid address.
Do this from Mail Flow>Rules
IF the sender is located outside the org
DO redirect the message to the catchall mailbox
DO (opt) prepend a disclaimer/prepend to the subject line
EXCEPT IF the recipient is a member of the allusers group