Si lo quieres hacer con like creo que sería más correcto lo siguiente :
Código:
//Descomponemos el nombre completo en nombre, apellido1, apellido2
DescomponerNombre(NombreIntroducido);
//Seleccionamos los registros coincidentes
Select funcion_concatena(nombre, apellidoP, apellidoM) as NombreCompleto
where Nombre like '%Nombre%' and ApellidoP like '%Ape1%' and ApellidoM like '%Ape2%';
La descomposición la puedes hacer porque el usuario introduce le nombre y los apellidos separados por espacios.
Un saúdo