You can run updatedb more frequently. By default it is run on a daily cron job and has the smarts to not run when on battery. (see /etc/cron.daily/mlocate)
You can also exclude directories in /etc/updatedb.conf that you don't want locate to index. I think in your case a more frequent cron job make sense. If run often enough, it finishes very quickly when running updatedb, which will you give you the instant search you're looking for.
Second the usefulness of rename, but beware there is some confusion about the name of the tool. It's called 'rename' on debian and derivatives and 'prename' on RH and derivatives.
