The way most geocoders work is by having street segments that are split at certain points and have from/to ranges of addresses. Here is a SO questions I asked many years ago that explains the logic:
http://stackoverflow.com/questions/10991330/how-does-the-goo...
In the US, a big chunk of OSM is based on a Tiger ingest. Tiger already had the segments split with the ranges (albeit some areas are not that accurate). In theory, you could still have a nice geocoder for US (the same is true for other countries like Germany).
The current crowdsourcing workflow of how people edit data in OSM makes it attractive for display (i.e. there is no need to split the street segments and add the address ranges for "pretty display"). But it also causes people to not edit the address ranges, snap the edges, etc, which just means that as a routing or geocoding dataset it is arguably actually worse.
You don't need _all_ the addresses to geocode. In theory, you could start with a particular country, clean it up for that problem. But right now, that is not the emphasis of OSM. The emphasis is a pretty base layer. For that OSM is awesome. For routing and geocoding, not so much.
Search for Navstreets Reference Manual for an example of Navteq's complicated schema for routing: https://www.google.com/search?q=navstreets+reference+manual
I really wish OSM was good enough for those two things... right now, it is not there yet.