Can ConcurrentDictionary.TryAdd fail?

Yes it can, here are the conditions (from msdn):

• ArgumentNullException - when the key is null reference
• OverflowException - when max number of elements was reached
• It returns false if an element with the same key already exist

Just to reiterate, this is nothing to do with concurrency. If you worry about two threads inserting an item at the same time then the following can happen:

• Both inserts work fine, if the keys are different.
• One insert works fine and returns true, the other insert fails (with no exception) and returns false. This happens if two threads try to insert an item with the same key and basically only one would win and the other would lose.

Sure it can. If the key already exists, the method will return false.

Ref: http://msdn.microsoft.com/en-us/library/dd267291.aspx

Return Value Type: System.Boolean true if the key/value pair was added to the ConcurrentDictionary successfully. If the key already exists, this method returns false.