Hmmm...
Maybe it depends on the kind of look-up you are doing, but it seems to be that in most cases it definitely needs to be sorted from low to high.
When I'm looking for an exact (unique) match, I often use the MATCH function to find index in the column for the matching value and then use that index in an INDEX function to pick up the right value in another column. I know it sounds like more work, but it causes me fewer problems.