to add to my last reply -
I disabled the built-in search field and put flexigrid inside my own search-page with several input fields. If you enter input-data that only 1 record matches, that record is shown,
else the input-data build a filter to mask out records and you can use the pagination system or sort records however you like.
Like misterakko pointed out, it comes down to the structure of the database beneath your website, use indexes on fields that you allow for sorting and circumvent sub-queries whenever possible - sorry for double post .. couldn't find edit button