Trying to follow the hints laid out here, but she doesn't mention how to handle it when your collection needs to return a value, like so:

    private delegate TValue DequeueHandler();
    public virtual TValue Dequeue()
    {
        if (dispatcher.CheckAccess())
        {
            --count;
            var pair = dict.First();
            var queue = pair.Value;
            var val = queue.Dequeue();
            if (queue.Count == 0) dict.Remove(pair.Key);
            OnCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, val));
            return val;
        }
        else
        {
            dispatcher.BeginInvoke(new DequeueHandler(Dequeue));
        }
    }

This obviously won't work, because dispatcher.BeginInvoke doesn't return anything. What am I supposed to do?

Or maybe I could replace dequeue with two functions, Peek and Pop, where Peek doesn't really need to be on the UI thread because it doesn't modify anything, right?

As a side question, these methods don't need to be "locked" either, do they? If they're all forced to run in the UI thread, then there shouldn't be any concurrency issues, right?