Ik denk dat nautilus sedert de 9 versies tracker niet meer gebruikt. Het gaat ook niet via locate: het zou anders veel sneller gaan, maar ook je meest recente bestanden niet vinden.
De zoeklijn van nautilus is zeer primitief, en werkt niet met wildcards of zo. Bestanden worden getoond waarvan hetgeen je zoekt voorkomt in de naam. Ik vermoed dat jij iets anders probeert, want bij mij lukt het een bestand te vinden door een deel van de naam te zoeken.
