My experience is also that (in the uk at least) it can't be done accurately with openstreetmap data.

For context, I've tried it! I've been working on a free library for geocoding UK addresses quickly and accurately. It comes with the caveat that you need access to the dataset of all addresses you're geocoding against - which could be your own list, or a commercial product like addressbase: https://github.com/robinL/uk_address_matcher/