This is something I have been craving from a long time! In fact, I had written few papers about this solution before some time.. Hooeey is a company who has implemented this idea in a nice way..
It solves a unique problem of having browser history distributed on different machines (if you are using more than one personal computers - which is very common these days!), it stores the history on a centralized place (their server) and lets you search through all the history.. (you can also create rules about what links you dont want to store in history, those links don't get transferred to the server!)
Video is worth million words, Take a look..