Well, i agree that the super search is getting rather huge and unwieldly. Although I do believe that most users have no concept of how to properly use this multiple select box.
An alternative approach that you might try can be seen here: http://www.phpcomplete.com/archives/200 ... one-right/
I'm not sure how this works in regards to browser compatability, but it works fine in firefox.
As the super search is getting so difficult to use, I would suggest a new, simpler search method. This may be similar to the old "power search", but I don't exactly recall how that worked. Amazon.com's search has been touted as a good example for other sites to follow. It is merely a text box where you can type in what you wish to search for, then under it there is a dropdown box that lets you choose what category you would like to search through. Something like this could be placed directly on the members' sidebar, and offer simple options like Title, Anime, Song, Song Artist, and Creator. I believe that this would satisfy most users search needs, and best of all, I believe you could just reuse code from the super search for it