You could have an extension that indexes everything the user goes to. The trick would be making it usable; I almost never use the "history" in my browser, because it tends to never find what I'm looking for. But if you try and solve it in a centralized way, you could do several interesting things:
* Make searches across all the sites you visited work better, maybe by creating better indexes of the content.
* Make the search work according to sites you visited the most (e.g. I'd prefer the search to find comments on HN before other things, then articles linked to from HN, etc.).
Such a service might be pretty useful: browser history that doesn't suck, and is persistent and accessible online. Anyone want to build it?