Yes, installing nautilus-data alone does yield a functioning gnome-search-tool.
apt-get --no-install-recommends -t testing nautilus-data -- hkp://keys.gnupg.net CA45 09B5 5351 7C11 A9D1 7286 0036 9E45 1595 8BC0
signature.asc
Description: OpenPGP digital signature
