I'm with Raymond in not wanting sets to maintain insertion (or any) order.  Even though I don't doubt that Larry--and no doubt other folks, from time to time--have a use for an "ordered set," I feel like it is bad practice to encourage that way of thinking about sets and using them.

Admittedly, I was only lukewarm about making an insertion-order guarantee for dictionaries too.  But for sets I feel more strongly opposed.  Although it seems unlikely now, if some improved implementation of sets had the accidental side effects of making them ordered, I would still not want that to become a semantic guarantee.

That said, having OrderedSet in collections module would be fine by me.  It might have different performance characteristics, but so what? It would be a different class that folks could use or not, depending on how they felt about its behavior and performance profile.