Why aren't my advanced search results sorting properly?
There's a setting in the Administer -> Customize Data and Screens -> Search Preferences called "Include Order By Clause". If you set that to "No" (presumably to improve performance as it recommends), then your search results will be ordered by contact id even when you try to change the sort order by clicking on the column headers.