Does anyone know of a more elegant way of doing an AND based search using Locate?

I want to use it to find my MP3's from a PHP script so I can access my music off a NAS device anywhere in the world.

currently I've come up with

locate -i akon |grep -i locked |grep -i up
this will find :-

Akon - Locked Up.mp3
03_akon_-_locked_up.mp3
locked_up-Akon.mp3

I tried to do a regular expression but it would only work in the order the words were in, but my RegEx is really poor.

I'm doing this on Debian Etch on an NSLU2 if it makes a difference.

I would really go back to using the regexp. It will be a lot better and cleaner once you understand it. Could you post what you were trying to use for the regexp.

regex doesn't play well with logical AND like that.
With (more) reduced data at each step, what's the issue with your current solution ?. Piping like that is normal in *nix. If you are really concerned about re-running the data, try and ensure the most restrictive parameter is passed to locate.