I just posted a beta version of HistoryHound that addresses a bunch of issues, not the least of which are support for Safari 4 and Opera 10.
Yes, you can now search your history in Safari 4, but it oddly doesn’t sort the results by relevance and it’s difficult to get to the history display in the first place. It still takes me longer to find something than it does in HistoryHound. For those of us that search through our histories frequently or use multiple browsers (I use Safari, Firefox, and NetNewsWire myself) HistoryHound is still what I’d choose (no bias here, of course 😀 ).
At any rate, hop over to the HistoryHound Beta Testing page to get the details and download a copy.