I made a supportcall to Microsoft and got this answer...
I am from the Messaging Developer Support team and have now taken ownership of this case. I’ve taken a look at the issue as you have described it in the forums, and based on the sample code there, the simple answer is that ExchangeService is not guaranteed to be thread safe except as a public static member (see http://msdn.microsoft.com/en-us/library/microsoft.exchange.webservices.data.exchangeservice(v=exchg.80).aspx ).
There are various techniques you can use to avoid the issue. You could use an ExchangeService for each thread, though this may not be advisable if you have lots of threads running at once as you may well hit throttling limits (each service instance may result in a new session on the server). You could implement a cache for folder objects, so that if different threads request the same object, the cache object can return it if it has already been requested (this would also increase performance as it would reduce requests to the server).
An important point to note is that as EWS is a web application, you should use multi-threading carefully, and minimise the number of worker threads. If each of the worker threads is generating requests to the Exchange server, then you are unlikely to gain much in performance terms as compared to using one worker thread, as you will be waiting on the response from Exchange.
So the solution in my case was to create a class called "SafeExecuter" which take care that only call to the Exchange per user is made at the same time. Also it takes care that the throttlingpolicy is not exceeded.