Desde o final de setembro de 2011, o PostGIS oferece suporte a consultas indexadas do vizinho mais próximo por meio de operadores especiais utilizáveis na cláusula ORDER BY:
SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;
... retornará os 10 objetos cujo
geom é o -90,40 mais próximo de forma escalável. Mais alguns detalhes (opções e advertências) estão nesse post de anúncio e o uso dos operadores <-> e <#> também está agora documentado na referência oficial do PostGIS 2.0. (A principal diferença entre os dois é que <-> compara os centroides da forma e <#> compara seus limites - não há diferença para pontos, outras formas escolhem o que é apropriado para suas consultas.) 
