When sorting a lookup column by clicking on the column header, the sort is lexical on the column index (= bound column). Should be lexical on the visible column.
Confirmed, thanks for the great description!
TODO: figure out if the same fix will improve sorting in forms and reports.