Так как нет подобного в поставке .NET использовал до этого Wintellect реализацию. Использовал успешно, но наткнулся на потолок ввиде производительности решения. Может подскажете как ускорить или найти уже готовое хорошее решение. Вот мои тесты и реализация внизу:

var wintDict = new MultiDictionary<int, int>();
var myDict = new MultiDictionary2<int, int>();

const int count = 1000000;

var t1 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Add(i, i);
});

var t2 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Add(i, i);
});

var t3 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Remove(i, i);
});

var t4 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Remove(i, i);
});

wintDict.Clear();
myDict.Clear();

var t5 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Add(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t6 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Add(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t7 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        wintDict.Remove(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

var t8 = Watch.Do(() =>
{
    for (var i = 0; i < count; i++)
        myDict.Remove(RandomGen.GetValue(10), RandomGen.GetValue(10));
});

Результаты:

(послед доступ)
t1 — 00:00:03.1043346
t2 — 00:00:01.1194840
t3 — 00:00:02.2321601
t4 — 00:00:00.2400655

(произвольный доступ)
t5 — 00:00:00.8711732
t6 — 00:00:00.2566774
t7 — 00:00:00.2513308
t8 — > минуты

Собственная реализация сделал Wintellect по всем тестам кроме удаления в произвольном порядке. Причина понятна косвенно (то что в wintellect не все так просто). Но как улучшить и этот показатель не теряя другие?

public class MultiDictionary2<TKey, TValue> : Dictionary<TKey, List<TValue>>
{
    protected readonly IDictionary<TKey, TValue> Inner;

    public void Add(TKey key, TValue value)
    {
        List<TValue> list;
        if (!Inner.TryGetValue(key, out list))
        {
            list = new List<TValue>();
            Inner.Add(key, list);
        }

        list.Add(value);
    }

    public bool Remove(TKey key, TValue value)
    {
        List<TValue> list;
        if (Inner.TryGetValue(key, out list))
        {
            var retVal = list.Remove(value);
            if (list.Count == 0)
                Inner.Remove(key);

            return retVal;
        }

        return false;
    }

    public bool Contains(TKey key, TValue value)
    {
        var list = Inner.TryGetValue(key);
        return (list != null) && list.Contains(value);
    }
}