At least here in the USA, address locations are not public data in most of the country. City maps are generally copyrighted and cannot be used in OpenStreetMap. Google has paid for access to proprietary address data. Osmand isn't a source of data, it is not at fault here. OSM contributors need to add addresses manually by walking down the street and using an OSM mobile app like StreetComplete to fill in the gaps.
So I'm no power user, but I've been using OsmAnd instead of Google Maps as a simple map app for about a year. If I just need Street names, fine. If I need to search for any business address, it sucks. I still need Google Maps on my device.
You say "contributors need to add addresses..." but this is so unintuitive that it's simply not going to happen in over 99% of cases. I say this as someone who really believes in the cause and who therefore makes up the 1% that would be willing to spend the time improving the data. (I still buy digital music and manually add my own mood/instrument tags, if you want a 'for instance')
So why don't I? Case in point: I wanted directions to a restaurant that opened near me about 2 years ago. Couldn't find it. So I walked there, ordered my food and while waiting for it to be served, manually navigated to the map position and found the previous restaurant was still listed. As far as I could see, there was no way for me to edit the map entry within OsmAnd. As an interested party, willing to invest some initial setup and learning time, and ongoing edit time of a minute or two, I completely failed. There's nothing in the UI to even hint at how to edit the address. A 'regular user' isn't even going to bother trying.
At this rate, the world will change much faster than the OSM data.
FWIW, I looked into it and apparently the "online search" functionality gets way more hits when searching for house numbers. That search must use nominatim or pelias as the backend. You can find it by hitting the search button, going to the categories tab, then scrolling to the bottom of that tab.
It really depends on the jurisdiction. Lots of cities and counties have open data, and lots of states too. There's also a national database that looks pretty interesting:
