Phrase matching works for probably 95% of my cases, but sometimes I get a phrase where I want to match the front and end, but not the middle. Wildcards would probably work just as well as regular expressions for me.
A more user-friendly option might be something like the interface for iTunes Smart Albums. "funny" AND "youtube" in my example above. or "funny" AND NOT "vimeo." I think the current behavior of "green + red = green" is the best default behavior, but it would be nice to be able to tweak it.