Is it a possibility to have some sort of offline database to query against ?
Or maybe that would make the app to heavy. Could be a "opt-in" download.
Including a dump of just lat/lon/rad->city from openstreetmap probably kilobytes. Including towns and features might be low megabytes.