Quando eu tive esse problema ainda no nautilus 43.alpha (o que acabava afetando a pesquisa de arquivos no shell também, era algum problema no tracker3 que eu não me lembro agora) eu desabilitava (FTS) Full text search, porém se eu não me engano o problema já foi resolvido, não tenho o link do commit no gitlab para consulta, a solução paliativa é simples e só está disponível via gsettings ou dconf-editor.
gsettings set org.gnome.nautilus.preferences fts-enabled false
Caminho no dconf-editor (não é aconselhavel fazer muitas modificações pelo gsettings ou dconf-editor caso não tenha certeza do que a opção vai fazer, SEMPRE leia com cuidado a descrição da opção)
É necessário reiniciar o nautilus após o comando com nautilus -q ou killall nautilus
Quando surgir alguma atualização do nautilus reative invertendo o comando para verificar se o problema foi resolvido.
OBS: Caso encontre algum problema no nautilus 43.X sugiro sempre verificar no gitlab
pois é a primeira versão do nautilus em gtk4/libadwaita e algumas funções podem ter alguns problemas que muitas vezes já forma corrigidos e a correção depende diretamente da atualização da sua distribuição.
#fui