En fait je vois pas de quoi tu parles avec la recherche
http://blogs.gnome.org/mccann/2012/08/01/cross-cut/ dit clairement qu'ils ont travaillé dessus pour la rendre plus efficace et moins couplé avec tracker.
Perso dans mon nautilus, j'ouvre la fenêtre et écrit 'Fedora' et je me retrouve avec tous les dossiers et documents relatif à Fedora qui se trouve dans mon home et ceux de façons récursive (ce qui fait que je me retrouve avec tous les dossiers maildir de mes archives mails dans les résultats).
Donc pour moi la recherche recursive, ça marche et même plutôt pas mal.