Encontrei uma aplicação chamada Pocket Pocket Query, PPQuery para os amigos

Basta ir ao site, fazer upload da pocket query (em .gpx ou .zip) e ele cria um ficheiro .jar que depois devem instalar no vosso telemóvel.
Depois de instalado o ficheiro estão prontos para o paperless geocaching. É possível consultar toda a informação disponível no gpx, descrição da cache, últimos logs e hint. Permite a pesquisa pelo nome, pelo código da cache, listar por ordem alfabética, por distância, ou mesmo, listar as últimas consultadas. Depois de seleccionar uma cache, permite ainda filtrar as mais próximas, e tem uma coisa chamada "multi assist", bastante útil para anotar gaitinhas.
Espero que seja útil para mais gente, ainda que o site apenas permita criar o tal ficheiro .jar para alguns modelos específicos de telemóveis.