Is there a way to add the gnome search tool to nautilus context menu so it starts from the current directory, like the 'Open in Terminal' context menu tool?
Probably nautilus-actions is what you are looking for:
sudo apt-get install nautilus-actions
Now start Nautilus-Actions Configuration Tool. If you don't want to click through the menus, just type "nautilus-actions-config-tool" in the [alt]+[F2] window.
This will start the nautilus-actions configuration gui in which you can configure new commands or scripts to be run from the context menu. The "help"-menu is quite detailed, you may want to have a look into it.
To just start gnome-search-tool from the context-menu, start the conf-tool, press [ctrl]+[n] (this will create a new action), check "Display item in location context menu", name it (Context Label), switch to the "Command"-tab and enter "gnome-search-tool" in the "path"-field. To start gnome-search with the current path, enter '--path="%d"' in the "Parameters"-box (see "legend" for other variables). Sometimes it is necessary to restart nautilus for the actions to show up (nautilus -q).
Some people experienced issues with the Ubuntu 11.10 repo version. If you have issues starting nautilus-actions, install the most recent version from here: https://launchpad.net/ubuntu/precise/+package/nautilus-actions
Example for the amd64-package:
wget http://launchpadlibrarian.net/84698667/nautilus-actions_3.1.4-1_amd64.deb sudo dpkg -i nautilus-actions_3.1.4-1_amd64.deb