One of my adverts in the 'attract' features gives a brief explaination of how the search features works to customers. I could imagine it would get very complicated to add a different search option as you mentioned. I know it may sound a bit primative, but why not have a short explaination of how to 'search' when you open the search tool? for example, I get lots of people say that they cannot find Ke$ha and artists like that, due to the symbols in the name etc. I put a little recommendation that customers search by the song name. Not ideal, but does the job.