How to implement RemoveAll for IDictionary, esp. a ConcurrentDictionary?

Question

I have the following method that I use to remove certain elements from an IDictionary:

public bool RemoveAll<TKey, TValue>(IDictionary<TKey, TValue> input, Func<KeyValuePair<TKey, TValue>, bool> predicate, Action<TKey, TValue> removalAction = null)
{
        var result = false;

        foreach (var kv in input.ToArray())
        {
            if (!predicate(kv)) continue;

            removalAction?.Invoke(kv.Key, kv.Value);
            input.Remove(kv.Key);
            result = true;
        }

        return result;
}

This method sometimes fails, if used for a ConcurrentDictionary. This can be frequently be reproduced using the following test:

public void RemoveAllFromConcurrentDictionary()
{
    var d = new ConcurrentDictionary<string, int>();
    for (int i = 0; i < 10000000; i++)
    {
        var key  = i.ToString() ;
        d.AddOrUpdate(key, k => i, (k, old) => i);
    }

    var tasks = new Task[]
    {
        Task.Run(() => RemoveAll(d,kv => kv.Value % 2 == 0)),
        Task.Run(() => RemoveAll(d,kv => kv.Value % 3 == 0)),
        Task.Run(() => RemoveAll(d,kv => kv.Value % 4 == 0)),
        Task.Run(() => RemoveAll(d,kv => kv.Value % 5 == 0))
    };

    Task.WhenAll(tasks).Wait();

    Console.WriteLine(string.Join("\n", d.Select(kv => kv.Key)));
}

If TKey is a non-nullable type this does not appear to happen.

My questions:

• Why is kv.Key == null, considering it is a struct (i.e. copy?) of the original element stored in the result of input.ToList()?

• AFAIK iterating over a ConcurrentDictionary or calling ToList() is per se thread-safe, possibly leading to stale results - but not crashing (e.g. with "collection has been modified while iterating"). What would be a thread-safe way to implement the intended functionality?

UPDATES:

• Regarding Remove vs. TryRemove: ConcurrentDictionary explicitly implements IDictionary<>.Remove by internally calling TryRemove.
• Thanks for noticing the result = false bug.
• Unfortunately, using ToArray does not resolve the issue - but thanks for the interesting insights!

The question was marked as a duplicate, but the linked, supposed duplicates do not address the main problem: how can kv.Key == null?