Thread safe Pooled Dictionary
Anytime that you check a count then do something on that you have to assume another thread did something in between. 

for example this code

while (q.Count &gt; m_poolSize)
{
    TValue localValue;
    q.TryDequeue(out localValue);
}


Because no locking is happening two threads could read the count and see it's over and both could remove an item.  Since you are using ConcurrentQueue both will remove different items.  This would cause your pool to drop below max size.  Maybe that's ok in your situation. 

Same issue is applied when having the Keys being a ConcurrentQueue.  In theory if you had your max pool size lower than the processor count times 2 and each thread hit that line at the same time you could get an exception, since you would try to dequeue when the queue has no items in it.  Granted this is an extreme example and one not likely to hit but at a min you would want to catch that exception. 

If you want to have the max stored in the pool you will need to do locking on an object and if we are going to do then both the ConcurrentQueue can go away.  The Keys I would replace as a list since that will do the array manipulation for us and change the ConcurrentDictionary values to just be a normal Queue.

private readonly ConcurrentDictionary&lt;TKey, Queue&lt;TValue&gt;&gt; m_pool;
private IList&lt;TKey&gt; m_keys;
private readonly object m_lock = new object();


We can simplify the Count method to use the concurrentDictionary GetOrAdd method

public int Count(TKey key)
{
    if (key == null)
        return 0;

    var q = m_pool.GetOrAdd(key, _ =&gt; new Queue&lt;TValue&gt;());
    return q.Count;
}


The Queue class implements ICollection and ICollection has a SyncRoot object.  To make it easy I would create a helper method so I don't have to cast to the Icollection each time I wanted the SyncRoot

private object SyncLock(ICollection collection)
{
    return collection.SyncRoot;
}


For the Request Method I would use the GetOrAdd again and lock on the return queue to know the count hasn't changed when Dequeued

public TValue Request(TKey key, Func&lt;TValue&gt; creator = null)
{
    if (key == null)
       return default(TValue);

    var q = m_pool.GetOrAdd(key, _ =&gt; new Queue&lt;TValue&gt;());
    lock (SyncLock(q))
    {
        if (q.Count &gt; 0)
        {
            return q.Dequeue();
        }
    }
    if (creator != null)
    {
        return creator();
    }
    return default(TValue);

}


TryAdd method now needs locking as well.  Plus we will use the ConcurrentDictionary GetOrAdd method and pass in the value to add so we can tell if it added to the dictionary or if it returned back an existing value. 

public bool TryAdd(TKey key, TValue value)
{
    if (key == null)
       return false;

    var addedQueue = new Queue&lt;TValue&gt;();
    var q = m_pool.GetOrAdd(key, addedQueue);

    lock (SyncLock(q))
    {
        q.Enqueue(value);
        if (q.Count &gt; m_poolSize)
        {
            q.Dequeue();
        }
    }

    // If these are the same then we added to the concurrent dictionary 
    if (q == addedQueue)
    {
        lock (m_lock)
        {
            m_keys.Add(key);
            if (m_keys.Count &gt; m_poolSize)
            {
                var ejected = m_keys[0];
                m_keys.RemoveAt(0);
                TryRemove(ejected);
            }
        }
    }

    return true;
}


Since we add to both the keys and concurrentdictionary then check to see if over we should init them with plus one of the max count

public PooledDictionary(byte maxPoolSize)
{
    if (maxPoolSize &lt;= 0)
        maxPoolSize = (byte)Math.Min(Environment.ProcessorCount, byte.MaxValue);

    m_poolSize = maxPoolSize;
    m_keys = new List&lt;TKey&gt;(maxPoolSize + 1);

    m_pool = new ConcurrentDictionary&lt;TKey, Queue&lt;TValue&gt;&gt;(Environment.ProcessorCount * 2, m_poolSize + 1);
}


In this implementation there is no need for while(q.Count > m_poolsize) as we controlling the adding an could only ever be one over the size.  Which is our trigger to remove one.