У вас что-то принципиально неверно с дизайном. ConcurrentDictionary используется, когда надо безопасно с многих потоков делать атомарные операции - put, get, put-if-absent, и т.д.. Операция идет на один ключ! Вы же хотите осуществить операцию над всеми ключами. Разумеется, у вас это не получается.

Вместо этого вам надо использовать SortedDictionary - там уже все будет храниться в отсортированном виде. А дл обеспечения потокобезопасности оборачивать доступ к нему в критические секции.