I would also recommend strengthening some of the tests with regard to 
ordering stability across update vs delete-and-reinsert.

TestOrderedDict.test_update does verify that updated items are not 
moved to the end, but the comment suggests it is only checking that the 
previous contents had not been cleared entirely.

test_iterators, test_popitem, and test_pop check only single 
insertions; I think the tests would be stronger if you updated the dict 
with reversed(pairs) before iterating, so that it would be obvious the 
ordering was based on the original insertion, rather than the latest 
access.

test_setdefault should also verify that x is the final key, and that 
the a key hasn't changed position.

I didn't see any tests for insert a, insert b, delete a, re-insert a, 
verify that a is now later than b.