Comment 2 for bug 1917152

It seems that search results are given by Tracker, which is a separate app dedicated to searching. This is a config option / design choice.

To fix this, Nautilus would need to ping D-Bus that the file has moved, Tracker see's this event and updates it's cache and again notifies D-Bus that this event has happened.

Nautilus needs to subscribe to this (not just a one time fetch) and update any view which shows this file.