Few weeks ago, I faced an interesting intermittent issue using the CRM Service, specifically with the RetrieveMultiple message. Basically, there was a WCF service wrapping the CRM Service and eventually we were getting the same issue you can find in this MSDN CRM forum post
After some deep investigation, it turned up to be a thread safe issue related to the way IServiceConfiguration and IServiceManagement are shared internally in the CRM libraries. IServiceConfiguration is not safe thread. Another important point to be considered was the early-bound types, which are not guarantee to be thread safe. (See http://technet.microsoft.com/en-us/library/gg326004.aspx).
Finally, a simple solution for this issue was to change the connection configuration:
CrmConnection crmConnection = new CrmConnection("myCRMConnection");
crmConnection.ServiceConfigurationInstanceMode = ServiceConfigurationInstanceMode.PerInstance;
using (CRMContext serviceContext = new CRMContext(crmConnection))
ServiceConfigurationInstanceMode.PerInstance is the key
Related to this topic, I recommend reading the new section Best Practices for Developing with Microsoft Dynamics CRM 2011, which is part of SDK 5.0.12 and newer ones.