Exchange Online, just as any other cloud service, is a shared environment where resources are pooled between multiple tenants. This means that certain limits need to be enforced, either to ensure that the services is being used as intended or to prevent that some users consume an uneven share of the available resources.
Luckily most limits, not all, are documented quite well in the Exchange Online Limits section of the Office 365 Service Descriptions. One of the tables on that page contains some limits with regards to recipients. See the following screenshot of this table as it was on the 10th of July, 2016: (click to enlarge)
And here is what recently changed:
A new Recipient proxy address limit was added to the table and immediately enforced.
Interesting is that the column for Exchange 2013 is populated with the value of 200 now too:
Unless a recent CU introduced a hardcoded limit I don’t think this is accurate. By my knowledge the real limit in the on-premises world is the character limit of the proxyAddresses AD attribute.
Now this may not apply to you, but there are an awful lot of people out there who have up to 300 or more proxy addresses. Some users created custom addresses for each mailing list of vendor account as Exchange never implemented a wildcard email address feature (firstname.lastname@example.org).
And to make matters worse, the admin interfaces do not allow to remove individual email addresses and then save the object again. A possible work around is to export all proxy addresses to CSV, remove them all, clean up the CSV to contain <200 entries and add them again with PowerShell.
The easiest long-term solution appears to be to add additional Distribution Groups where your mailbox is the only member. Now add a bunch of those addresses to the DG to ensure you can still receive all messages sent to the addresses.
In hindsight this would’ve been a perfect topic for Microsoft to announce before implementing the change, including guidance for customers who are impacted by this change.