I would try to make it more explicit that updates do not reset the 
order, but deleting a item and re-inserting it *does*.  (So it isn't 
the first insertion of the key, it is the first that hasn't yet been 
followed by a deletion.)

Maybe change:

"""
When iterating over an ordered dictionary,
the items are returned in the order their keys were first added.
"""

to [removed "first", added longer explanation]

"""
When iterating over an ordered dictionary,
the items are returned in the order their keys were added.  (This 
implies that updating an item to a new value does not reset the order, 
but deleting the item and re-inserting it moves the item to the end.)
"""