Thread-safety based on object value
According to MSDN, all public and protected members of ConcurrentDictionary&lt;TKey, TValue&gt; are thread-safe and may be used concurrently from multiple threads. However, concurrency only applies to the individual actions performed on the instance of the ConcurrentDictionary. The situation will not get messy, if a thread is performing a write operation and an another thread is performing a read operation at the same time. But, there is no protection within the  ConcurrentDictionary class against the situation, when an information of the past is provided, that has since changed and because of that, an invalid operation is performed. 

I do not see the reason of calling ContainsKey, since an another thread could remove that particular element between the ContainsKey and the Dictionary value accessor operations and KeyNotFoundException will be thrown.

if (_processingGateways.ContainsKey(request.GatewayId))
// the element could be removed right at this point during execution
    _processingGateways[request.GatewayId].WaitOne(); // KeyNotFoundException is thrown here
_processingGateways.TryAdd(request.GatewayId, new AutoResetEvent(false));


The key to your solution could be the TryGetValue method. It is going to lock the ConcurrentDictionary for reading and return the element (if it exists).

if (_processingGateways.TryGetValue(request.GatewayId, out var Gateway))
    Gateway.WaitOne();
_processingGateways.TryAdd(request.GatewayId, new AutoResetEvent(false));


(Disclaimer: code uses C#7.0 out variables)

Now your are secured against the exception. 

If you inspect the code for possible deadlock situations, you might observe that it is possible, that Set gets executed before WaitOne. It is good to know, that the wait returns when all events are set and it does not matter, whether or not that happened before or after wait was called. Great, no deadlocks here!