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.
They're great and we have many friends at both companies. Our main goal is to get map data and software into the open so others working toward that goal are not really competitors.
If there's overlap, I don't see why that's a bad thing. The geo industry has had the problem of too few options for a while. More options are a good thing.
We host Pelias at Mapzen and you can check out the autocomplete as well as fulltext search here: https://mapzen.com/projects/search