It sounds like the crux of the problem is in the NLP (natural language processing) part of the problem: turning a search string into a useful query on the database, and perhaps ordering the results in terms of relevance.

 Here, Marc Wick of Geonames says that their gazetteer is freely available and uses a mix of NLP, statistics, and heuristics.  Apparently, some details of the implementation can be found in The Geospatial Web.  Does TOPP have a copy?

 This diploma thesis looks like it might have some solid and implementation strategies described in it.