В очередной раз припёрло.
Надо переизобрести как можно более шустрый велосипед с вот таким вот интерфейсом:

  interface IStorageIndex<T> // для всех T есть EqualityComparer, для большей части - ещё и Comparer<T>
  {
    // index изменяться не будет, value - не уникальное. Распределение заранее неизвестно.
    void AddIndex(T value, int index);
    void RemoveIndex(T value, int index);

    int[] IndexesOf(T value); // обязательно O(1).
  }

Подозреваю, что много не выжать — индекс на ~5 млн элементов уже сейчас строится за секунду-две. На практике коллекции будут в пару-тройку тысяч элементов, но зато их будет несколько десятков и изменяться они будут достаточно часто.

Все реализации "в лоб" идут нос к носу — надо копать в сторону алгоритмической сложности. Как пример:

  internal class StorageIndex<T>: IStorageIndex<T>
  {
    private Dictionary<T, SortedSet<int>> valueIndexes;
    private SortedSet<int> nullValueIndexes;

    public StorageIndex(IEqualityComparer<T> valueComparer)
    {
      this.valueIndexes = new Dictionary<T, SortedSet<int>>(valueComparer);
      this.nullValueIndexes = new SortedSet<int>();
    }

    private bool TryGetIndexes(T value, out SortedSet<int> indexes)
    {
      bool result;
      if (value == null)
      {
        indexes = nullValueIndexes;
        result = true;
      }
      else
      {
        result = valueIndexes.TryGetValue(value, out indexes);
      }
      return result;
    }

    public void AddIndex(T value, int index)
    {
      //EnumerableCode.ValidIndex(index, "index");
      SortedSet<int> indexes;
      if (TryGetIndexes(value, out indexes))
      {
        if (!indexes.Add(index))
        {
          //Code.Bug(@"Indexing already indexed value.");
        }
      }
      else
      {
        indexes = new SortedSet<int>() { index };
        valueIndexes.Add(value, indexes);
      }
    }

    public void RemoveIndex(T value, int index)
    {
      //EnumerableCode.ValidIndex(index, "index");
      SortedSet<int> indexes;

      bool removed = false;
      if (TryGetIndexes(value, out indexes))
      {
        removed = indexes.Remove(index);
      }
      if (!removed)
      {
        //Code.Bug(@"Removing index on non-indexed value.");
      }

      if (value != null && indexes.Count == 0)
      {
        valueIndexes.Remove(value);
      }
    }

    public int[] IndexesOf(T value)
    {
      SortedSet<int> indexes;
      return TryGetIndexes(value, out indexes) ?
        indexes.ToArray() :
        new int[0];
    }
  }

Может, на RB tree поменять?