I consider this issue as lying on the way to using the orderable of dict in OrderedDict implementation (the latter is very desirable because current OrderedDict implementation can be easily broken by using plain dict API). The main difficulty of implementing OrderedDict is the move_to_end() method (especially move_to_end(False)).

In additional, the problem of holes is occurred for any often modified dictionary. Using ordered dict in lru_cache() give as good stress test for optimizing dict updating and resizing code.

I don't suggest to change lru_cach() implementation just now. But after long testing ordered dicts during the developing stage of 3.7 (or even 3.8) we can make a decision.