That's an internal nautilus thing, I believe, and has nothing to do with Places->Search. Nautilus' search uses beagle when available, which is different from gnome-search-tool -- Beagle is installed but the Places - Search menu is not updated https://launchpad.net/bugs/52878