I can't think of anyone that had a universal search interface before Spotlight came out in OS X. i.e.: a single search box that searches not just files, but contacts, emails, etc - all without having to specify what type of thing your looking for (this last part is important! It's a key part of the patent).
From 1999, before the Apple patent was filed in 2000 and Spotlight announced in 2004:
"Copernic 99 is intelligent software that can search the Web, newsgroups, and email simultaneously, using more than 30 information sources."
I was using Copernic on my Windows machines at work back around 2000. It was pretty cool. At night (or any other programmed downtime) it would go through each new file, email, web history, etc and index all the keywords to be ready for your next search.