Well the first thing is that you have to add the validation to the results page and not the search page directly. Since the search page submits to the results page, it is the page that needs the server validation.
Remove the server validation from the search page. It is odd though... it appears to be applying without a trigger value. What did you put in as the trigger when applying the server behavior?