А что тут сложного? Объединение трёх поисков по регулярке с нужной сортировкой. Только запрос получится небыстрый.
SELECT `FIO` AS `fio`, 1 AS `position`
FROM `test`
WHERE `FIO` REGEXP CONCAT('^ *', :needle)
UNION SELECT `FIO`, 2
FROM `test`
WHERE `FIO` REGEXP CONCAT('^ *[^ ]+ +', :needle)
AND NOT `FIO` REGEXP CONCAT('^ *', :needle)
UNION SELECT `FIO`, 3
FROM `test`
WHERE `FIO` REGEXP CONCAT('^ *[^ ]+ +[^ +] +', :needle)
AND NOT `FIO` REGEXP CONCAT('^ *[^ ]+ +', :needle)
AND NOT `FIO` REGEXP CONCAT('^ *', :needle)
ORDER BY `position`, TRIM(`fio`);