Tente isso
WHERE contact_first_name IN (".implode(', ', array_fill(0, count($search), '%s')).") OR contact_last_name IN (".implode(', ', array_fill(0, count($search), '%s')).")
ATUALIZAÇÃO
A resposta correta para esta pergunta é A consulta está correta, são os parâmetros dinâmicos que estão errados que fazem com que a sintaxe da consulta fique errada. Na verdade, estava na seção de comentários logo abaixo desta resposta, então mesclei com as respostas aceitas!
