Someone should build a good, open, web API-based search for OSM data. Not everyone cares about 100% offline capabilities, and improving search would be a massive gain in usability for OsmAnd and other OSM clients.
I'm pretty sure this exists, but the tooling around OSM all seems pretty obscure and badly documented. There aren't really flagship apps, which I'd argue there should be. It took me a lot of research (on official OSM pages) to find Organic Maps.
I don't see why Lucene couldn't be used for this application.
Why could it? Don't you somehow have to teach it which words are synonyms and common combinations for autocomplete etc.? It seems to me at least that this is where the major work would be, and even then it's expensive to run this for the whole world just for free.