C# exception: Key is not present in the dictionary

I got a little problem. Sometimes, when I try to call the following code, the remove methods throw an exception with the message "the key is not present in the dictionary".

private Dictionary<IPAddress, ARPHostEntry> dIPHostTable;
private Dictionary<MACAddress, ARPHostEntry> dMACHostTable;

public HostTable()
{
    dIPHostTable = new Dictionary<IPAddress, ARPHostEntry>();
    dMACHostTable = new Dictionary<MACAddress, ARPHostEntry>();
}

public void AddHost(ARPHostEntry arphEntry)
{
    lock (dMACHostTable)
    {
        if (dMACHostTable.ContainsKey(arphEntry.MAC))
        {
            dMACHostTable.Remove(arphEntry.MAC);
        }
        dMACHostTable.Add(arphEntry.MAC, arphEntry);
    }
    lock (dIPHostTable)
    {
        if (dIPHostTable.ContainsKey(arphEntry.IP))
        {
            dIPHostTable.Remove(arphEntry.IP);
        }
        dIPHostTable.Add(arphEntry.IP, arphEntry);
    }
}

The class ARPHostEntry is a simple calss which holds an IP-A开发者_运维知识库ddress and an associated MAC-Address where both fiels in this class are read-only. The program is multi-threaded, but I lock the dictionarys in this class every time I use them.

I am helpless. Why do this exceptions occour?

with best regards

Edit

For clarification, the accepted answer is correct. The generated exception was an issue caused by cross-thread access to my dictionaries.

The Remove method shouldn't throw such exception, it should return false if key not found (See here). Instead of removing and adding, why don't you try updating the value of the key?

It's unclear from your example if you're truly sharing the host tables across threads. Shouldn't the private host tables also be static?