Многопоточность, блокировка доступа

Я бы начал с ReaderWriterLockSlim или ReaderWriterLock:

В этой документации приведён полноценный пример использования. Краткая суть в том, что читать могут сразу несколько потоков. Писать может только один. Читающий поток может захотеть писать и тогда он запрашивает блокировку на запись , что предотвращает появление новых читателей, пока объект не освободится и не завершится запись. Читатели, на время, пока объект заблокирован и происходит запись, ждут. Максимальное время ожидания регулируется вами.

Для реализации более гранулированной блокировки вы можете объявить "корзины" для элементов, которые находятся в процессе чтения и "корзину" для элементов, находящихся в процессе правки, то есть использовать не один а два или более экземпляров ReaderWriterLockSlim. Однако, будьте осторожны. Грануляция блокировок всегда черевата мёртвыми блокировками (deadlock).

Представьте, что в вашем MyList два объекта и вы решили блокировать их отдельно. К вам одновременно приходят два запроса. Один - на чтение, другой на запись.

1. Первый поток забрал первый элемент MyList на чтение.
2. Второй поток забрать второй элемент MyList на запись.
3. Первый поток начал ждать освобождения второго элемента. Он хочет его почитать.
4. Второй поток начал ждать окончания чтения первого элемента. Он хочет его исправить.

Вы в ж... я хотел сказать в deadlock-е. Именно по этому так полезно указывать конечное значение timeout при обращении к ReaderWriterLockSlim.

Ну или сразу согласиться, что экземпляр ReaderWriterLockSlim будет один и на запись будет блокироваться весь ресурс целиком. Тогда deadlock-и вам не страшны.

Окей, вам по идее нужен fine-grained lock. То есть блокировка не на уровне всего списка, а на уровне одного элемента.

Кроме того, раз вы ищете элемент по ключу, имеет смысл воспользоваться Dictionary.

Для этого давайте оснастим элемент списка объектом для блокировки. Выйдет что-то такое:

class Wrapper<T> // это будет одновременно и обёртка, и объект для блокировки
{
    public T Value;
    public bool IsAlive = true;
}
Dictionary<string, Wrapper<MyStruct>> MyDict = new Dictionary<string, Wrapper<MyStruct>>;
object Lock = new object();
void AddItem(string key, MyStruct value)
{
    lock(Lock)
    {
        MyDict.Add(key, new Wrapper<MyStruct>() { Value = value });
    }
}
void ModifyItem(string key)
{
    Wrapper<MyStruct> wrapper;
    lock(Lock)
    {
        if (!MyDict.TryGetValue(key, out wrapper))
            return; // нет такого (уже)
    }
    // получить данные можно под внутренние блокировкой:
    MyStruct oldValue;
    lock (wrapper)
    {
        if (!wrapper.IsAlive)
            return;
        oldValue = wrapper.Value;
    }
    // теперь у нас есть данные, можно с ними долго работать
    /* тут длинные вычисления */
    // для модификации нужно залочить снова wrapper
    lock (wrapper)
    {
        if (!wrapper.IsAlive)
            return; // упс, наш элемент тем временем удалили
        wrapper.Value = newValue;
    }
}
void DeleteItem(string key)
{
    Wrapper<MyStruct> wrapper;
    lock(Lock)
    {
        if (!MyDict.TryGetValue(key, out wrapper))
            return; // нет такого (уже)
    }
    // модифицируем 
    lock (wrapper)
    {
        if (!wrapper.IsAlive)
            return;
        wrapper.IsAlive = false;
    }
    lock (Lock)
    {
        MyDict.RemoveKey(key);
    }
}

Если у вас зависимые данные, вам нужно для обработки залочить несколько элементов. Для этого, чтобы избежать deadlock'ов, имеет смысл лочить их в фиксированном порядке (например, по возрастанию ключа).

void ModifyItems(IEnumerable<string> keys)
{
    var materialKeys = keys.OrderBy(k => k).ToList();
    List<Wrapper<MyStruct>> wrappers = new List<Wrapper<MyStruct>>();
    bool lockSuccessful = true;
    lock(Lock)
    {
        Wrapper<MyStruct> wrapper;
        foreach (var key in materialKeys)
        {
            if (!MyDict.TryGetValue(key, out wrapper))
            {
                lockSuccessful = false;
                break;
            }
            wrappers.Add(wrapper);
            Monitor.Enter(wrapper);
        }
    }
    if (lockSuccessful)
    {
        // мы получили данные, работаем с ними
        /* тут длинные вычисления */
    }
    lock (Lock)
    {
        foreach (var key in materialKeys.Reverse())
        {
            Monitor.Exit(wrapper);
        }
    }
}

Если вам неинтересно в конце ModifyItem убедиться, что значение ещё живое, можно всё упростить.

Dictionary<string, MyStruct> MyDict = new Dictionary<string, MyStruct>();
object Lock = new object();
void AddItem(string key, MyStruct value)
{
    lock(Lock)
    {
        MyDict.Add(key, value);
    }
}
void ModifyItem(string key)
{
    MyStruct oldValue;
    lock(Lock)
    {
        if (!MyDict.TryGetValue(key, out oldValue))
            return; // нет такого (уже)
    }
    // теперь у нас есть данные, можно с ними долго работать
    /* тут длинные вычисления */
    // для модификации нужно залочить снова wrapper
    lock(Lock)
    {
        if (!MyDict.ContainsKey(key))
            return; // удалили тем временем
        MyDict[key] = newValue;
    }
}
void DeleteItem(string key)
{
    lock(Lock)
    {
        MyDict.RemoveKey(key);
    }
}