Opino que dado que el problema está en el usuario y la entrada incorrecta de datos, sean estos los que se traten a la hora de insertar en la base de datos. Yo pasaría todos los datos susceptibles de búsqueda por una regexp que eliminase tildes, puntos, etc...
Aplicaría el mismo criterio a los valores introducidos en la búsqueda también.
No se solventaría toda la problemática, pero parte

Saludos