Nominatim, which I worked with at MapQuest Open when it launched, is a great geocoder for purely OSM data. We built Pelias (https://github.com/pelias) at Mapzen because Nominatim is not built to handle autocomplete. We also wanted to start with a fulltext search engine -- Elasticsearch in this case -- instead of Postgres with search logic on top of it. We also wanted to search other open datasets like the fast-growing OpenAddresses.

We host Pelias at Mapzen and you can check out the autocomplete as well as fulltext search here: https://mapzen.com/projects/search