Google Search History is cool and all, but it requires to to be logged into google to use it. The problem with that is that it requires you to leave your GMail account logged in, too.

Sorry, Google, that's no good to me. Yahoo does it much better – it identifies you and your search history, but requires you to enter your password again when accessing Yahoo mail.