I'm not really sure whether I understood it right - but I may suggest a layout I made on the mockup.
This way we may have a usual set of criteria, which are empty by default ("Search criteria"), and a list of current search criteria ("Current search"), the ones which are used in the users list. If we want to set some "filter", we set up the values in "Search criteria" and press "Search". "Current search" list is then filled with those we set, and the list of users is filled with "filtered" ones. "Search criteria" is cleared so we may create a new one from the scratch.
If we want to edit the criteria we set at this moment, we may press "Edit search" button. It reloads the page with "Search criteria" filled-in with current values (the same as in "Current search"), and we may just edit them and press "Search" again so these edited values are used. There may also be a button to clean up the values in "Search criteria".
So if this interface is ok, I may try to code it