http://cuil.com
It's new, so I have seen a little bit of slowness, I did a search on a couple of words that didn't come up with any results. I believe they went live today, so I am sure they are still working out kinks, but if this is as promising as it sounds, I might switch over from google.
yeah, I said it.
here is an excerpt from their "about us" page at http://www.cuil.com/info/
We believe that analyzing the Web rather than our users is a more useful approach, so we don’t collect data about you and your habits, lest we are tempted to peek. With Cuil, your search history is always private.