Tal y como has puesto la select, se debe de dar las ocurrencias en el mismo orden, por eso puede que no te salgan, teniendo en cuenta lo que dices, deberías poner algo así, aunque sea lento
SELECT nombre, apellido1, apellido2 FROM tnombre
WHERE CONCAT( nombre, " ", apellido1, " ", apellido2)
LIKE "%Perez%" AND CONCAT( nombre, " ", apellido1, " ", apellido2)
LIKE "%Juanito%" AND CONCAT( nombre, " ", apellido1, " ", apellido2)
LIKE "%Lopez%";
Creo que esto debería funcionar
Un saludo
