Probablemente debería representar países/ciudades como polígonos en la base de datos y luego usar funciones de intersección de polígonos al estilo de OpenGIS para intersectar.
Pero , MySQL no implementar la intersección de polígonos correctamente (solo MBR - Rectángulo delimitador mínimo). Entonces, este enfoque, aunque correcto en teoría, simplemente no funcionará para usted con MySQL. Es posible que desee considerar cambiarse a Postgres.
Lo que puede hacer es usar las capacidades de intersección MBR de su base de datos y complementarlas con su propio código que hace la intersección de polígonos/puntos (puede encontrar bibliotecas que hagan esto).