Anecdotally, I've found OSMand's search functionality to vary between OK and completely unusable. Especially when entering addresses, OSMand really struggles to interpret what should be quite straightforward entries.

While I haven't extensively used OrganicMaps, I found its search functionality to behave much better.