Options that I see to address this:
1* set(dK, V) should store (dK, V) and get(nK) should do a reverse look up if nK is not found
ISSUE: This may break new code that iterates and expects nK in the iterator.
2* set(dK, V) & set(nK, V) should store both (dK, V) and (nK, V)
ISSUE: increases the number of stored key/values.
3* keep current set/get logic and make iterator() to return 'duplicated' entries for deprecated values (dK, V) & (nK, V)
ISSUE: complexity in the iterator logic as well.
4* keep track in Configuration of the key used regardless of being deprecated or not and return those on iterators()
ISSUE: it will require Configuration to have an additional data structure to keep track of deprecate values being used. This will add more complexity to the configuration.
I'm inclined to do either #2 or #3.