OR condições quando não estão no mesmo campo ou intervalo baseado (como < , > , LIKE ) realmente diminui a capacidade do MySQL de tirar vantagem dos índices; você pode reestruturar as consultas dividindo-as em outras mais simples separadas que você pode então UNION. Separá-lo assim permite que o MySQL aproveite um índice diferente de cada consulta dentro dos UNIONs SELECT `u`.`user_id`, `c`.`company`
FROM `users` AS `u` LEFT JOIN `companies` AS `c` ON `c`.`user_id` = `u`.`user_id`
WHERE `u`.`user_id` = 'search_term'
UNION DISTINCT
SELECT `u`.`user_id`, `c`.`company`
FROM `users` AS `u` LEFT JOIN `companies` AS `c` ON `c`.`user_id` = `u`.`user_id`
WHERE `u`.`lname` LIKE 'search_term%'
UNION DISTINCT
SELECT `u`.`user_id`, `c`.`company`
FROM `users` AS `u` LEFT JOIN `companies` AS `c` ON `c`.`user_id` = `u`.`user_id`
WHERE `u`.`email` LIKE 'search_term%'
UNION DISTINCT
SELECT `u`.`user_id`, `c`.`company`
FROM `users` AS `u` INNER JOIN `companies` AS `c` ON `c`.`user_id` = `u`.`user_id`
WHERE `c`.`company` LIKE 'search_termeo%'
;
Além disso, observe que alterei o JOIN do último para um INNER, pois qualquer condição na tabela à direita de um LEFT JOIN (que não é "sem uma correspondência dessa tabela") é basicamente um INNER JOIN de qualquer maneira.
UNION DISTINCT é usado para evitar que registros que satisfaçam várias condições sejam repetidos, no entanto... se companies.company não for exclusivo (ou seja, o ID da empresa 1 chamado "Blah" e o ID da empresa 12 também chamado "Blah"), eles também serão mesclados onde não estariam em sua consulta original; se for um problema em potencial, isso pode ser remediado incluindo company_id em cada SELECT . 
