> Whenever I hear "ordered hash" then I think of a hash whose keys are
> ordered according to a definable order - not necessarily insertion order.

You are right.

> In fact, insertion order seems to me a very special case.  Is this really
> widely used?

It's not uncommon. And not meant to replace comparison -based ordered ADTs.