O que você tem deve funcionar, mas pode ser reduzido a:
select * from table where concat_ws(' ',first_name,last_name)
like '%$search_term%';
Você pode fornecer um exemplo de nome e termo de pesquisa em que isso não funcione?
select * from table where concat_ws(' ',first_name,last_name)
like '%$search_term%';
