alex.cameron made this change in WT-5678 for __wt_hs_cursor_position(). There are other places in the code where we have to make the same fix.

Summarizing the issue:
HIstory store keys do not maintain the same ordering as the respective btree keys, so we can not rely on that ordering when we search_near and iterate in either direction based on key compare.

Solution:
Construct a history store key from the given btree key and use that in comparison to determine the direction to walk in (or to retry search).