You are getting a 302 instead of a 404 because you are using the onError attribute in your configuration. This tells PrettyFaces, that you want to redirect the user to another URL (the one with the id “error”) in case of validation errors.
Just remove the onError attribute and you should get a 404!
Sorry, but I think this is currently not possible. You can either redirect the user to some other page with a 302 using the onError attribute or you can send a standard 404 result code. If you use the latter, PrettyFaces will execute HttpServletResponse.sendError(404) using the standard Servlet API.
If you want to be able to show different error pages depending of the page the user tries to access and the specific validation error, you should think about whether it is possible to do this validation when the user submits the search form or something like this.