No, me refería a usar
REGEXP en la consulta SQL. Primero, lees la cadena que te piden buscar desde PHP, y con algún algoritmo (que lo tienes que idear tú) creas una expresión regular que represente a esa cadena con o sin acentos (ahí sí quizás usaría str_replace). Por otro lado, si se busca "hallaz" también tendría que encontrar "hallazgo" si usas los "%" también al final. ¡Suerte!