I don't know if it is your thing, but running "slocate myfil.foo" from a
terminal emulator is how I would do it. "slocate -u" may need to be run
first to update the database if it is not handled automatically (But it
should be the same database that nautilus uses, I think). *disclaimer*:
I'm frozen back on Ubuntu 10.04, but I'd be really surprised if that
program is not present in whatever the newest version is.