For perspective: I tried to buy a Harvard Business Review article PDF today, but the Web site required that I create a username and password instead of simply taking my credit card and giving me the PDF. So I googled for the name of the article, plus the term "PDF", and was able to steal a copy in seconds. (Somebody had uploaded it to their server, probably without any intention of sharing it or knowledge that Google would find it.) People don't like wasting time.
What's crucial here is the design. First, you have some means of tracking user history which is absolutely private, persistent over months, and very very easy to install. The obvious choice is a Firefox plugin which background-uploads your history to a Web app. That's the easy part.
The hard part is that you then leverage Google's ability to do
site:xyz.comsearches. But instead of specifying one
site:, you specify the hundreds or (more probably) thousands that were visited within a given period of time. The hard part is that this capacity may be locked inside a giant corporation's policy decisions. Your best-case scenario is that it's locked inside a giant corporation's API documentation, which is almost just as painful.
Google co-operation seems unlikely as you'll be competing with Google Web History. However, Google Web History looks well-intentioned but stupid, and it'll be fucking wicked if somebody actually builds this. There may be almost-as-good search engine alternatives to Google which offer superior APIs; if so you can make something incredibly awesome in a very short space of time and make life better for everybody.
If you're a Firefox plugins wizard who knows of a great API-friendly search engine, ping me on Twitter. If you just cut to the chase and build this while I'm twiddling my thumbs and calling it a great idea, hey, you win. Rock on.
I suppose making peace with the shortcomings of Google Web History is a win too, but I get skeptical that an app is going to respect my time when I have to log in just to find out if it's any good in the first place.