I would side with Inada in thinking they both give the same amortized complexity, but beyond that, benchmarks are the real answer.  There is little value in keeping the current implementation of OrderedDict *if* benchmarks show that it is rarely faster.