My 5¢ worth:
1: the cross-field search bug/error needs to be fixed
2: make the current standard search box pinnable, so that if you only want to do a quick search, it will have the current behaviour. If you need to do a series of searches - eg. making up a playlist - it will stay open.
3: change the Custom Search so it "remembers" the input selection filters, not the "search". So when opened to a previous search, the fields would be set up and waiting for your input. eg. last custom search was "artist"/"is" and "genre"/"is not" and "decade"/"is any off", the Custom Search window would open, populated with those three criteria, waiting for new input in the artist, genre, decade fields
Added:
The "OR" and "AND" commands from WMP, if implemented, could use "/" and "+" respectively