Problemas con Escape en URL amigable

[ElecktroFocko]

Estoy creando una web con URL's amigables y las estoy implementando en el sistema de búsqueda.
Es decir, si buscó "foobar", debiese quedar así: www.sito.cl/Buscar/categoria/foobar y efectivamente, hasta ese punto esto tengo todo listo....
Peroooo...

Si busco "Ñandú", me entrega la URL "escapada": www.sitio.cl/Buscar/categoria/%D1and%FA y esta URl ya no es amigable .

Me puse a averiguar, y por ejemplo, si busco nuevamente "Ñandú", pero en www.mercadolibre.cl, la URL que entrega es como lo que yo busco hacer: www.mercadolibre.cl/Ñandú

¿Como lo hago para que me funcione?

Les explico como realizo un poco el proceso que realizo para tener las URL amigables

En el index.php principal de mi sitio, existe un buscador, en el cual se ingresa una categoría y un texbox con las palabras a buscar...

El "Action" del form del buscador envía los datos a "transformar.php", el cual redirige a través de la función:

Código PHP:

  header("Location: "); 
   

El código que tiene ese transformar.php es el siguiente:

Código PHP:

  <?php include_once("clases/php/main.php");
if(isset($_REQUEST['Buscar']) && isset($_REQUEST['categoria'])){
    
    $buscar = $_REQUEST['Buscar'];
    /*$find = array('á', 'é', 'í', 'ó', 'ú', 'ñ','ü');
    $repl = array('a', 'e', 'i', 'o', 'u', 'n','u');
    $buscar = str_replace ($find, $repl, $buscar); 
    $find = array(' ', '&', '\r\n', '\n', '+');
    $buscar = str_replace ($find, '-', $buscar);*/
    $buscar = str_replace (" ", '+', $buscar);
    
    if($_REQUEST['categoria'] != 0){
        $res=mysql_fetch_row(mysql_query("SELECT nombre FROM clas_categorias WHERE id = '".$_REQUEST['categoria']."'"));
        $nom_categ = $res[0];
        $find = array('á', 'é', 'í', 'ó', 'ú', 'ñ','ü');
        $repl = array('a', 'e', 'i', 'o', 'u', 'n','u');
        $nom_categ = str_replace ($find, $repl, $nom_categ); 
        $find = array(' ', '&', '\r\n', '\n', '+');
        $nom_categ = str_replace ($find, '-', $nom_categ);
 
    }else{
        $nom_categ = "Todas-las-categorias";
    }
    
    $url_amigable = "Buscar/".$_REQUEST['categoria'].":$nom_categ/$buscar";
    header("Location: "._ABPATH.$url_amigable);
}
?>   

Entonces, cuando uno clickea "Buscar" y el form del buscador se envía, me redirige a donde debe, pero con mi URL "escapada" y no amigable (para el visitante al menos)

PD: No puedo reemplazar los caracteres con acentos ni con la "ñ" por una "n", porque el textbox del buscador sigue mostrando la variable obtenida por $_GET['Buscar'], entonces, si los remplazo y un visitante busca "Ñandú", efectivamente la URl será amigable y sería algo como "/categoria/Nandu", pero en el etxbox de este, aparecería "Nandu" en vez de Ñandú, y o es la gracia...

¿Como podré solucionarlo?

Muchisimas gracias de antemano
Gonzalo Zúñiga