I confirm I have exactly the same problem in 1.9.4.
16,498 tickets in bdd for 197,975 threads (ie : table ost_ticket_thread).
SQL Example when problem occurs :
SELECT DISTINCT COALESCE(B1.ticket_id, B2.ticket_id, B3.ticket_id, B4.ticket_id)
FROM (
SELECT object_type, object_id, MATCH (search.title, search.content) AGAINST ('mysearch' IN BOOLEAN MODE) AS `relevance`
FROM `ost__search` `search`
WHERE MATCH (search.title, search.content) AGAINST ('mysearch' IN BOOLEAN MODE)
) `search`
LEFT JOIN (
select ticket_id as ticket_id from ost_ticket
) B1 ON (B1.ticket_id = search.object_id and search.object_type = 'T')
LEFT JOIN (
select A2.id as thread_id, A1.ticket_id from ost_ticket A1
join ost_ticket_thread A2 on (A1.ticket_id = A2.ticket_id)
) B2 ON (B2.thread_id = search.object_id and search.object_type = 'H')
LEFT JOIN (
select A3.id as user_id, A1.ticket_id from ost_user A3
join ost_ticket A1 on (A1.user_id = A3.id)
) B3 ON (B3.user_id = search.object_id and search.object_type = 'U')
LEFT JOIN (
select A4.id as org_id, A1.ticket_id from ost_organization A4
join ost_user A3 on (A3.org_id = A4.id) join ost_ticket A1 on (A1.user_id = A3.id)
) B4 ON (B4.org_id = search.object_id and search.object_type = 'O')
LEFT JOIN ost_ticket A1 ON (A1.ticket_id = COALESCE(B1.ticket_id, B2.ticket_id, B3.ticket_id, B4.ticket_id))
LEFT JOIN ost_ticket_status A2 ON (A1.status_id = A2.id)
WHERE ((A1.staff_id=16 AND A2.state="open") OR A1.dept_id IN (4,5,21) OR A1.team_id IN (3,5) AND A2.state="open")
ORDER BY `search`.`relevance` LIMIT 500
FYI this query return :
500 rows in set (3 min 5.04 sec)
Nb : I am not forced to use space in the search to reproduce it
NB2 : Sometime search seem fine --> When data allredy cached by mysql I presume
I will try to upgrade it to 1.10 in few day on a lab (it a vm, i can snapshot it) and feedback in this thread