This situation differs from that in earlier versions of Exchange. In those versions, later calls against the same folder are faster than the original call.
Note This workaround is applicable only if the same criteria is used every time. If the search criteria constantly changes, you may have to try an alternative method, such as a sort-and-seek process. For example, a search that is based on a particular datetime value would not use consistent criteria.