Track your slow query log and look at your recent searches that happen about the same time. Check the words that are being searched for and if they are overly common, remove them from the search index. For instance on a vBulletin related website, you shouldn't allow searches for vBulletin as it will occur in too many places to be useful. If your site is about flowers than flower can be eliminated. It may mean that your users have to get more creative but that shouldn't cause too much harm. They should get more relevant results.
You can see what people searched for in the query column of your search table. This is cleared every hour so you might want to adjust the query for this in includes/cron/cleanup.php. It is this code:
PHP Code:
//searches expire after one hour
$vbulletin->db->query_write("
DELETE FROM " . TABLE_PREFIX . "search
WHERE dateline < " . (TIMENOW - 3600) . "
### Remove stale searches ###
");
Having these records stored for a longer period of time during your investigation shouldn't cause too many problems and would allow you to track things down easier.