I've been using the latest MSN Desktop Search with the MSN Toolbar. The latest version adds tabbed browsing to Internet Explorer, but I turned it off. Similar to when I spent several weeks with Firefox, I just didn't feel comfortable with the tabs. I'm just too used to ALT+TAB and ALT+F4 to navigate. I know CTRL+TAB and CTRL+F4 will do the same, but why bother?
Anyway, the Desktop Search is excellent and I've loaded up many more IFilters to expand it's capabilities.
I'm wondering if a IFilter exists for browser history and the registry - although I don't know if search UI would be able to take advantage of them. More details to come.