I realise that I am bit late to the party, but I would like to point out that a smaller, arguably simpler, and almost certainly faster alternative design exists.

This design simply consists of an array of (prev, next, key) nodes attached to the base dict.

The linked list is maintained using the prev & next pointers of the nodes as normal.

The mapping of keys to nodes is maintained by ensuring that the index of the node in the node array matches the index of the key in dict-key table.
When the size of the array matches that of the keys table, this should be a very fast operation.

When the dict is resized, the array will need to resized. 
(Possibly lazily if PyDict_* functions are used directly on the ordered dict.)

Size analysis
-------------

For an an occupancy of X, 
Eric's design takes 7/X + 3 slots per key/value pair.
The alternative design takes 6/X slots per key/value pair.

For an occupancy of 50%, half way between the minimum of 1/3 and maximum of 2/3,
on a 64bit machine:
The design proposed in this issue takes 17 slots or 136 bytes per key/value pair.
The alternative would take 12 slots or 96 bytes per pair, about 70% of the size.