Correct way to delete elements from a ConcurrentDictionary with a predicate
I know it's not a direct answer to your question, but I'm trying to get to the roots of the problem rather than giving correct answer to issue caused by potential misuse...

In your code what you are actually trying to do is to write a cache with time-based expiration of items. Even though ConcurrentDictionary is thread-safe, it's not quite appropriate structure for frequent element scans like you do. Moreover, in your code you remove items, then add them back in case when they have been updated in the middle. It causes side effects for other threads that may try to read the value in-between.

Correct solution would be to use a proper data structure. If by any chance you are using .NET 4.0 or later .NET has already provided you with proper solution - MemoryCache class, otherwise I would recommend creating a lock-based class that maintains 2 indexes for entries - a Dictionary for storing key-value pairs, and a SortedList for storing expiration timestamp-key mapping. In this case you'll always know upfront when the next expiration will happen so timer can be set to specific TimeSpan, and you don't have to scan through all cache entries to find expired ones.