Many thanks Jan! Based on this description, I now avoid sort/2 on variables (since their relative ordering may change during execution at some point in the future) and use list_to_set/2. Both list_to_set/2 and group_pairs_by_key/2 in the SWI library rely on the following important property of keysort/2: After keysort/2, pairs with the same key (which may also be a variable) occur in adjacent positions. This is prescribed by the ISO standard and therefore a very reliable and nice property that will no doubt hold in all future versions.
I think list_to_set/2 should be mentioned a bit more prominently in connection with term ordering and sorting. Maybe in the documentation of sort/2, as a more predictable (though slower) alternative when variables are involved? Thank you!