First, sure, CPython's only about two orders of magnitude slower than C, so on big enough data sets, the asymptotic performance rules. N log N is 100 times better than N^2 as soon as N is over about 1000. (The obvious-to-me way to implement an ordered map in Python would be to maintain a dict and a sorted list of keys; inserting N items into a sorted list is N^2.)
Second, this kind of data structure might be fast in PyPy. Like, C-like fast, or worse in the constant factors by only a factor of 2 or 5. Certainly you could imagine JIT optimizing dynamic language implementations where that was the case. But I haven't tested.
Third, usually not.