The problem with 'locate' and with Spotlight is that it doesn't search every file. It used to be possible to work-around this by updating the updatedb as root, which would warn you that was a potential security hole (i.e. anyone with read access to the database could get a list of every file in any user's $HOME) but since most Mac users are the only user on their computers, that was not a huge concern.
I finally got so fed up that I wrote my own script which will:
- make a plain-text index of every file, link, and directory
- search that index using
- offer to restrict searches to $HOME or the current directory if certain arguments are given
- if nothing is found in the index, offer to update the index, or search with
You can download the script here [Dropbox link]. It should be fairly easy to understand how it works just by reading through it.