The 13.04 nautilus (currently 3.6.3) does not have recursive search enabled which does work quite well.
There's been 2 updates since initial packaging, really isn't too hard to enable, too bad for users if it isn't..
https://bugs.launchpad.net/ubuntu/+s...s/+bug/1077415