When does a dictionary throw an IndexOutOfRangeException on Add or ContainsKey?

I agree that this is almost certainly a synchronisation issue.

I'm not aware of any documentation that describes exactly when and how this can happen - the behaviour is undefined if you use a dictionary in a non-threadsafe manner.

For testing in your dev environment, I'd suggest running some parallel threads that randomly insert, remove, update etc in a continuous loop (basically a "concentrated" version of what's happening in your production environment).

The documentation for Dictionary states:

A Dictionary<TKey,TValue> can support multiple readers concurrently, as long as the collection is not modified. ... To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

If you are not synchronizing access to the Dictionary, then you might get issues like those you describe (presumably because the internal state is no longer valid). If you want to try and reproduce this in your development environment, then try creating a program that uses multiple threads to continuously read and write from a Dictionary without synchronization.