tl;dr

When incoming email gets rejected, check if you have records in mail-enabled entities (contacts, accounts, queues, and system users OOB) using the same email address.

I’ve done this today

• Set up a hybrid server-side sync for a customer. (There are some gaps in the docs, this is a recommended reading companion.)
• Add a support queue and a mailbox for support@foobar.com
• Set Convert Incoming Email to Activities to “All email messages”
• Approve email
• Test & enable mailbox. Inbound – success, outbound – success)
• Test it myself: outbound email works like a charm, inbound email gets delivered to the support mailbox but not to the queue. Er?

So I’ve done a bit more:

• Permissions – all good – I’m admin
• Workflows – none

Time to troubleshoot:

• Open Settings > Email Configuration > Server-Side Synchronization Monitoring – Mailbox Errors trace shows up lots of error code 29 entries – “incoming email rejected”. I can see that – you’re NOT helping, error log!
• Boogle the problem. Yep, people reported it here, here, here, and here, and here. No definite resolution.
• All hail on-premises – enable tracing.

ErrorCode: -2147218683, InnerException: Microsoft.Crm.CrmException: At least one system user or queue in the organization must be a recipient
at Microsoft.Crm.Common.ObjectModel.EmailService.FindBestOwner(AddressManager addressManager, TrackingInfo trackingInfo, AddressEntry[][] allResolvedAddressEntries, String traceSubject, Int32& ownerObjectTypeCode, ExecutionContext context)


Now, that is interesting, because, even with the glasses on (not that I need any just yet), I can see the queue with the support@foobar.com email address. Read forum entries a bit more closely. That one has couple people reporting the issue caused by inactive queue having the same email address.

But I don’t have any other queues? Wait a minute! What about other records? I’ll be damned, there is a contact support@foobar.com created at around the same time as I was tinkering with the mailbox. Delete the contact, test again – everything works!

Theory

I’m the owner of the mailbox so my personal email setting will apply

When mailbox is tested, system will send email to support@foobar.com from, you guessed it, support@foobar.com. Mailbox is not approved yet so the sender is not known, the system goes ahead and creates a contact, according to my settings.
Then the system decides to resolve the recipient, and finds two addresses. Wouldn’t be a problem but there is a new organization-level setting that allows unresolved recipients:

With the recipient unresolved, CRM throws an exception (see above).

This is just a theory, of course, but the problem is real and resolution is real – check for duplicate emails in mail-enabled entities in your organization, and make sure to check the inactive records too.