Here is the (in my opinion) most user-friendly alternative to regexp filtering.
Very easy to do.
" " (space) = AND
" -" (space, minus) = NOT
Boolean searching. Case-insensitive.
"happy -mp3 -xxx" finds matches containing "happy" and not containing "mp3" or "xxx"
"fun -wmv -avi -mpg -mpeg -jpg" finds files containing "fun" while not being a image or video.
So you, for example, search for "deeds" (you want to find the new movie) and filter with something like this:
"-jpg -txt -html -(old date)" etc. The old date you'll see in the search results, the old movie will be there too, I guess.
Search-as-you-type would be terrific here, because you immediately see how search results get less and more precise.
It's fast, ist's very easy to use and a boolean "AND" and "NOT" is quite simple to do, I guess. And because there are no regexps that have to be correct, search-as-you-type woulnd't be a big problem, too. onChange of the input field's data, a new search os done within the search results.
Need more ideas?