OSM and OsmAnd seem great except when you want to search for something. If I search for "mcdonalds" typed lazily I get 5 results hundreds of miles away. To find the local Mcdonalds restaurant I have to type "McDonald's" very specifically. This lack of fuzzy search makes these apps unusable.

Its an unfortunate situation of the two parties involved in this software each pointing at each other and blaming the other with neither willing to budge.

OSM, I would argue rightly says it's up to map makers how to query the data their project puts out there. The app makers claim (this sounds like BS) that OSM's data or API makes that too hard to do.

Either way absolutely unusable. If TomTom can just make a search that works better than this and layer that over the OSM data they've got a win IMO.

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 don't see why Lucene couldn't be used for this application.