*incoming wall of text*

Seeing as Office 365 is such a hype right now, I decided to create a catch-all address for a customer of ours on his personal Exchange Server 2013.

=== Still to do, because lazy –> add pictures for more attractiveness 🙂 ===

According the t3h intarwebz, this is supposed to be easy.
Unfortunately one only gets half the info when having to configure this.
A couple of trial-and-error moments later, the following checklist lead to the result needed (also applicable in an Office 365 environment btw)

1. Go to https://your_server/ecp/ (or https://outlook.office365.com/ecp/) and choose ‘mail flow’ in the left column.
2. Go to the ‘accepted domains’ menu on top and make sure the domain to which the catch-all address is to be assigned, is set as domain type ‘internal relay’.
   I will explain why.
   In a next step we will create a server-side mail rule for the catch-all mailbox. In order for a NDR to not appear when we send a mail, we need to make sure the domain is set to ‘internal relay’. This causes mail rules to be executed before the server actually checks if the mailbox exists, thus enabling a filter possibility.
3. Next, we want to create a mailbox in which we’ll drop all the catch-all mails (unless you already have a user or shared mailbox set up to receive this, of course)
   I’m not going to go in a lot of detail on this, as this is rather basic stuff on an Exchange Server (left menu ‘recipients’, top menu ‘mailboxes’, blah blah…)
4. Not always optional (especially not literally doable in O365) –> restart your Microsoft Exchange Transport service on your Windows server. (if you have the classic white-paper setup with a front- and backend server, restart the service on both servers)