This one seems pretty simple; set up some rules for ordering, then simply test if the ordered lists match the rules.

int sum = 0;
foreach (var update in updates)
{
    bool valid = true;
    for (int i = 0; i < update.Count; i++)
    {
        for (int j = i + 1; j < update.Count; j++)
        {
            if (!rules.ContainsKey(update[i]) || !rules[update[i]].Contains(update[j]))
            {
                valid = false;
                break;
            }
        }
    }

    if (valid)
    {
        sum += update[update.Count / 2];
    }
}

Also, I did find a small bug in my input... I was getting some blank lines at the end of my input, so I was tossing those away in my input fetching code. Today's input was split into two parts (rules and lists), seperated by a blank line, and that blank was getting filtered out, causing some weird behavior. Whoops!

Modified it to only throw out blank lines at the end, so all is good now.

Oh boy - initially I'm at a loss on how this should be fixed. My first idea is simply, when an invalid rule is found, to start shuffling them when an invalid order is found. So if A,D,B,C is in the wrong order, I would swap to A,B,D,C, then A,B,C,D. Might be a bit expensive, but eh, I'm sure it'll work.

private void fixUpdateList(List<int> update)
{
    for (int i = 0; i < update.Count; i++)
    {
        for (int j = i + 1; j < update.Count; j++)
        {
            if (!rules.ContainsKey(update[i]) || !rules[update[i]].Contains(update[j]))
            {
                (update[j], update[i]) = (update[i], update[j]);
            }
        }
    }
}

That... worked far better than I thought. Sweet.