Crea un índice sobre el campo `city`, eso puede ayudar un poco a resolver el problema.
Si no hay diferencia, hay que forzarlo a usarla.
Procura usar EXPLAIN para ver el resultado del parser:
De ese modo podremos ver por dónde está fallando la consulta.