Me gustaría volver a tu algoritmo descripto para hacerte una reflexión:
Cita: 1. Se comprueba cada palabra de mi_columna (no solo el principio de la frase) si hay palabras que empiezan por "par" descartando las que contiene pero no al principio (ej: "acaparado")
2. Al encontrar palabra que empieza con "par" se compara dicha palabra (palabra entera esta vez ) ej "para" o "paracoches" con el array $palabras_excluidas
3. Si en el punto 2. se encuentran solo palabras excluidas se considera respuesta NO VALIDA y descarta esta fila
4. Si en el punto 2 se encuentran palabras excluidas pero también NO Excluidas se considera respuesta VALIDA y se agrega esta fila a la respuesta
5. Si en el punto 2 se encuentran solo palabras No Excluidas se considera respuesta VALIDA y se agrega esta fila a la respuesta
Es a mi entender, absolutamente imposible hacer una única consulta que pueda responder a las cinco condiciones al mismo tiempo. Para lograrlo tienes por lo menos, que iterar el resultado del primer paso, para poder resolver el segundo, y no existen consultas iterativas en MySQL.
¿Lo has tenido en cuenta?
Se necesita:
1) Extraer un grupo de N palabras.
2) Comparar las N palabras con una colección de palabras.
3) Si las palabras recolectadas están incluidas totalmente en el segundo conjunto, descartar todo, en caso contrario (los siguientes están lógicamente incluidos), recuperarlo.
El problema es que las dos primeras partes son incompatibles para una consulta, porque no puedes extraer las palabras sin iterar...
Tal vez sea posible hacerlo con un stored procedure, pero yo te recomendaría usar una combinación de programación y consultas.