Same issue, OsmAnd is great, but unless geocoding services like Nominatim get as good as Google Maps's search, I cannot use it unless I know the precise location of where I'm going.