Often, an algorithm that requires iteration in a certain order is a sign that you are keeping information implicitly in the ordering instead of explicitly in a more appropriate data structure. You also may be trying to pack lots of unrelated functionality into a single object when multiple objects would serve better.
But it's hard to say without better examples, and there are times when you do want order and lookup. Can you give a couple situations where you want ordered dictionaries?
Right now I'm working on a large data set where there is a set of players and each player has a score. I'm using a Python dictionary from player ID to the player score, but I also want an easy way to grab the top N players from the set. The players' scores are updated continuously, so the quick mapping from a player ID to their updated score is also critical (if the scores were constant I'd just put it in a list, sort it, and be done with it).
Hmmm, does an ordered dictionary actually solve this problem? It seems like you want to retrieve based on player id, but get the top N based on score. An ordered dictionary would be ideal if you wanted to retrieve and get the top N based on the same key.
I guess you could use two data structures, with one of them being an ordered dictionary. But then the ordered dictionary doesn't actually have to support lookup; you could just use a heap.
But it's hard to say without better examples, and there are times when you do want order and lookup. Can you give a couple situations where you want ordered dictionaries?