Others that I can think of are IXQuick (not sure if they use their own index or not) and Yioop (smallish index). There really is a lack of large players indexing the web.
Its also possible that we will see the rise of niche search engines, such as iconfinder.
Today's search engines are not just indexes of web pages. They give direct answers for "when did Lincoln died", they show detailed street and satellite maps with StreetViews in search results, they act as business directory, they act as people finder, they have elaborate image search (again super expensive to do), they recognize objects in images, they have freshest news search for thousands of sources, they can do video search, they have scans of 100s of thousands of books, they catalog millions of products and so on. Even getting some of this high quality data such as satellite maps, books, business listings, product catalogues etc would cost ~100 million dollars in licensing deals.
Even if you decided to get world's most productive programmers you will need at least 300 people in my most minimal estimation and more than 2-4 years before you can build anything that has non-negligible chance of competing. That's about $75M of cost per year right there at the ultra-minimal end. Of course, this is assuming you already had bigger breakthrough than that of PageRank and that you can beat state of the art machine learning and natural language processing techniques. Hopefully you can now see, for all intent and purposes, search business is closed to attack via startups. I can imagine Facebook and Apple would sooner or later get in to this business but it would be uphill battle for them primarily because of lack of talent that search engine business requires and more importantly lack of data that only Google has for billions of queries and users doing them. You can build AirBnB with smart college hires but building search engines needs truly the cream of the crop who are perfect rare blend of Computer Scientists and part time mathematicians while also being an exceptionally productive applied programmers. Google has been working for years to sweep away pretty much all talent in this area and it would take most competitors significant effort to build this kind of army.
PS: DuckDuckGo is not a "real" search engine. It has a very little of its own index and for most queries they just rearrange results fetched mostly from Bing while inserting links from their own little index. If Bing shuts them out for leaching off of them, they would be toast.
I can't tell you what the answer is, but I am pretty sure that it's outside the box you've built yourself into.
What those neither of those give you is an up to date index, which is why small search engines still need Yahoo and Yandex's APIs. I'm not sure any free resource can match the speed at which big companies can index the web.
The real problem imho is building a distributed index and fighting spam. Both are incredibly hard problems to do well and very expensive. Hence so few are trying to do it.
I tried building a small search engine with a very basic algorithm and it worked very well for 90% of searches.
I agree with you in part but I also believe if you got the others 100% right you would have a respectable engine by itself.
IIRC google used to scan different pages at very different frequencies. Quite possibly because it has assigns pages into subsets every time it indexes.
DuckDuckGo makes a business not tracking users and I believe made over 1.2 million last year based on its donations.
A search engine doesn't need to track people to make money, they just make much more money if they target ads better by tracking.