The C version should defend itself against any key-changes during iteration (see the state counter used in deque objects for an example of how to do this).   The pure python version of OrderedDict has only minimal defenses against mutating during iteration, and it should be left as-is.

FWIW, "surprising" is in the eye of the beholder.  When it comes to mutating containers during iteration, all kinds of things can happen (that is why databases implement reader and writer locks).  

The following results in an infinite loop:

    s = list('abc')
    for k in s:
        s.append(k)