Search on the desktop has been tried (and is being tried) today: Unity (of Ubuntu) and Gnome Shell (of Gnome 3) are mostly search-focused interfaces (interestingly, Unity worked much better for me at finding the right stuff, and it was based on Xapian vs the Gnome provided tracker based on Lucene IIRC).

On Ubuntu (recent versions have Gnome Shell, older versions had Unity), press the "Windows" key, and type away...

There's certainly a lot to complain about in both of those implementations (esp speed), but to get a feel for what such UX would look like, try them out.