EWS API Search Filter does not return all informat

I have the following scenario: I check a mailbox to which emails with some relevant information are sent to to get the information from it.

I use a lot of search filters to find the specific email and to get the correct one:

var collection = new SearchFilter.SearchFilterCollection(LogicalOperator.And);
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "text1", ContainmentMode.Substring, ComparisonMode.Exact));
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "text2", ContainmentMode.Substring, ComparisonMode.Exact));
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "text3", ContainmentMode.Substring, ComparisonMode.Exact));
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "text4", ContainmentMode.Substring, ComparisonMode.Exact));
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "text5", ContainmentMode.Substring, ComparisonMode.Exact));
collection.Add(new SearchFilter.ContainsSubstring(ItemSchema.Body, "longer string 1", ContainmentMode.Prefixed, ComparisonMode.IgnoreCase));

But now I have the problem that I do not always find the correct email messages. I tested that very simple: I sent a message to that mailbox I am polling that looks completely equal to another message. In both cases all information from above are included. But then, after I changed something on my SearchFilters or anything I suddenly see the correct result, the latest message.

I have no idea what could cause the problem, because it's so ungeneric.

Your query looks very complex and would be very costly in terms of Server performance. Eg your Search Filter will need to be converted to a MAPI restriction and then applied to the server https://technet.microsoft.com/en-us/library/cc535025(v=exchg.80).aspx the way you keep applying multiple sub-strings I doubt will be reliable unless the data-set your querying is quite small. Because Restrictions are cached by the server the behaviour your seeing is probably just the time the backend is taking to build or refresh the restriction. (eg if your query the same thing again and get a really quick response that would indicate a cached result) or its just the process of forcing the new one being created which is finding the newest items first.

You would be much better served by either making your search filter much simpler and dealing with more items at the client side where the text can processed by many different methods. Or look at using AQS (or KQL in 2013) https://msdn.microsoft.com/en-us/library/office/dn579420(v=exchg.150).aspx then you doing Keyword queries of the Content indexes (which is what the Search process is optimised for). While you might get more false positives this way it should be a lot quicker and more reliable and filtering the false positives at the client is much easier.

If you want to use Rest Cache you need to use Raw Soap as i don't believe the Managed API will support it. Its an Attribute of the QueryString Element eg

    <?xml version="1.0" encoding="utf-8"?>
    <soap:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
                   xmlns:m="http://schemas.microsoft.com/exchange/services/2006/messages" 
                   xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types" 
                   xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
      <soap:Header>
        <t:RequestServerVersion Version="Exchange2010" />
      </soap:Header>
      <soap:Body>
        <m:FindItem Traversal="Shallow">
          <m:ItemShape>
            <t:BaseShape>IdOnly</t:BaseShape>
            <t:AdditionalProperties>
              <t:FieldURI FieldURI="item:Subject" />
            </t:AdditionalProperties>
          </m:ItemShape>
          <m:IndexedPageItemView MaxEntriesReturned="1" Offset="0" BasePoint="Beginning" />
          <m:ParentFolderIds>
            <t:DistinguishedFolderId Id="inbox" />
          </m:ParentFolderIds>
          <m:QueryString ResetCache="true">subject:Autodiscover</m:QueryString>
        </m:FindItem>
      </soap:Body>
    </soap:Envelope>