Hi,
Though I havent much used EWS, I found some points.
Firstly, what version of Exchange are you using ?
Secondly, you could use paging even if you query didn't timeout. Check this:
http://blogs.msdn.com/b/exchangedev/archive/2010/03/12/throttling-policies-and-the-ewsfindcountlimit.aspx[
^]
If you implement paging and fiddle with optimal page size which will be under 1000 and also reduce the properties your retrieving down to those you actually using this should help solve the problem and increase the performance of your application.
The default timeout with the EWS Managed API is 90 seconds and is set on the ExchangeService Object. You can set this to a higher value e.g to set it to 5 minutes
If the server is busy for a time or any other environmental this can happen . I would suggest you check the EWS.Log on the Exchange server to see what happened at that time.
Regards,
Praneet