I just had a huge light bulb go off CT, if you go over to HPOF.com they have exactly what your talking about on their Advanced Search. Yeah, you have to sign up for it to see this page I think (not positive) but it will show the page how I'm understanding you would like it for Multiple Select fields and that it does work or the value can be nulled.

I think they did this by setting the mandatory on the join pages but then disabling it on all other pages, including the search page. When the mandatory see more is killed on the search page then it works much better.

Question, not sure if it will work for you or not, but can you set the fields you want to "Mandatory" on your join page and then create a new set that is "Not Mandatory" on the Search page and have it run the search without selecting the "Not Selected" field? On POF.com's Advanced Search page it has a field for "Select" and then an option of None Selected before the list and you can choose everything on it or nothing. Check it out, it might be the best way to describe this if it's what your looking for. I'd suggest code stripping but the site is in asp not php so that probably won't work.

But it's a place to start your explanation.