I'd like to propose an entirely different approach: use AVL trees for colliding strings, for dictionaries containing only unicode or byte strings.

A prototype for this is in http://hg.python.org/sandbox/loewis/branches#avl
It is not fully working yet, but I'm now confident that this is a feasible approach.

It has the following advantages over the alternatives:
- performance in case of collisions is O(log(N)), where N is the number of colliding keys
- no new exceptions are raised, except for MemoryError if it runs out of memory for allocating nodes in the tree
- the hash values do not change
- the dictionary order does not change as long as no keys collide on hash values (which for all practical purposes should mean that the dictionary order does not change in all places where it matters)