As explained in a previous post (Exchange 2013 – Search results limited to 250), there is reported bug in Exchange 2013 that limits the search results to 250.

Microsoft released CU11 (Exchange 2013 – CU 11 released) that was supposed to fix (among others) this bug. Unfortunately, after updating and testing… no success.

I opened a case support, and my assigned tech confirmed in a customized lab what I had tested previously: The CU11 did not solve the bug as reported on the KB3093866 is not updated with this procedure

After consulting with the development team, the tech indicated that an additional configuration parameter (in addition to CU11) was needed on the exchange servers to raise the search limits:

The following configuration file must be changed…

%ExchangeInstallPath%/Bin/Microsoft.Exchange.Store.Worker.exe.config

…to add the following registry key after the </runtime> line:

<appSettings>
<add key="MaxHitsForFullTextIndexSearches" value="1000" />
</appSettings>

This example limits the search results to 1000. The value must be in the range 1-1000000.

My Microsoft.Exchange.Store.Worker.exe.config file now looks like this:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <runtime>
    <generatePublisherEvidence enabled="false"/>
    <disableCommitThreadStack enabled="1"/>
  </runtime>
  <appSettings>
    <add key="MaxHitsForFullTextIndexSearches" value="1000" />
  </appSettings>
</configuration>

I modified it yesterday and today the change was applied without restarting any service.
To apply it immediately, restarting the MSExchangeIS service should be enough.

At present (02/11/2016) the official KB3093866 is not updated with this procedure.

Update (02/19/2016)
The KB3093866 has been finally updated as well as a new post created by the assigned tech on the Microsoft technet blog: "Solución al límite de 250 resultados cuando realizamos una búsqueda de emails en Exchange Server 2013"