para serte sincero la razón porque ocurre este error de las url no estoy seguro solo se que pasa y como solucionarlo en la mayoría de los casos....
o del buscador depende que tan complejo seria, pero básicamente solo necesitas crear un formulario con N cantidad de variables y enviarlas por post o get a una pagina X que tu definas, en esa pagina utiliza un loop personalizado que revisa esta(s) variable(s)
revisa esta documentación para que sepas que variables puedes enviar y como crear tu loop
http://codex.wordpress.org/The_Loop http://codex.wordpress.org/Class_Reference/WP_Query http://codex.wordpress.org/Function_...ce/query_posts
yo suelo usar la información del primer y segundo link, tu puedes usar la del primero y tercer link ya es cuestión de gustos y que se adapte a lo que necesitas.