What is a good desktop search tool?

One tool I can recommend is tracker. If you install the software, it is started automatically when you log in. It updates its index as a background process. If you want to search some item, there are different possibilities:

1. Nautilus: Press Ctrl+f. A windows opens where you can enter your search term.
2. GNOME applet: The deskbar applet allows you to enter a search term and shows a listing of found things.
3. Catfish: is a application which can talk with different search programs.
4. Console: enter tracker search foobar and tracker will start its search. Type tracker for a full list of available commands.

I use recoll. It's very nice.