In recent Nautilus releases (3.5.x, 3.6.0, up to the latest Git version 302fb4d), entering anything into the search box returns no results; the status bar forever remains at "Searching..."

Nautilus also prints the following messages to stderr:

(nautilus:1202859): GLib-GObject-WARNING **: invalid (NULL) pointer instance
(nautilus:1202859): GLib-GObject-CRITICAL **: g_signal_connect_data: assertion
`G_TYPE_CHECK_INSTANCE (instance)' failed
** (nautilus:1202859): CRITICAL **: nautilus_search_provider_set_query:
assertion `NAUTILUS_IS_SEARCH_PROVIDER (provider)' failed
** (nautilus:1202859): CRITICAL **: nautilus_search_provider_start: assertion
`NAUTILUS_IS_SEARCH_PROVIDER (provider)' failed
** (nautilus:1202859): CRITICAL **: nautilus_search_provider_stop: assertion
`NAUTILUS_IS_SEARCH_PROVIDER (provider)' failed
** (nautilus:1202859): CRITICAL **: nautilus_search_provider_set_query:
assertion `NAUTILUS_IS_SEARCH_PROVIDER (provider)' failed
** (nautilus:1202859): CRITICAL **: nautilus_search_provider_start: assertion
`NAUTILUS_IS_SEARCH_PROVIDER (provider)' failed

(In reply to bug 681587 comment #5)
> @Mantas: yes, please file that as a separate bug report, possibly with a
> backtrace before the first warning (set the environment variable
> G_DEBUG=fatal_warnings before running it in gdb to make it break at the first
> warning).

The first warning, unfortunately, is about failure to connect to Tracker, so "nautilus_search_provider" functions are not reached with fatal_warnings enabled. (I have libtracker-sparql installed, but not Tracker itself.)

If I recompile with --enable-tracker=no, simple search starts working fine...