Linq query performs poor according to performance analyzer in VS2012
I think the crux of your problem here is you are using the wrong tool for the job. The purpose of a dictionary is usually for direct retrieval i.e. give me the value associated with X key. I'm not sure how optimized they are for O(n) queries.

To rule out the ConcurrentDictionary&lt;TKey, TValue&gt; being the bottleneck, you could try switching it out for something like a ConcurrentBag&lt;T&gt;.