I don't know that either of them actually do this, but you might try either SafariStand or SAFT. They are the two major enhancer plug-ins for Safari. I know both of them offer alternate ways to view history, including the ability to search history (at least SAFT does this).
I don't personally use either. They're just off-the-top-of-my-head recommendations. But you may find something you like, in any event, in one/both of them.