Pues no sé que tanto complicarse .. desde un primer momento hubieras puesto lo que estás haciendo y ya estarias disfrutando de tu código .. Usa la función urlencode() que para eso está y olvidate de problemas ..
Código PHP:
echo "<a href=\"nose.php?titulo=".urlencode("Esto está aquí con eñes y demás caracteres")."&otravar=".urlencode("otra más con eñes y espacios")."\"">Link con variables con espacios</a>";
y en nose.php
Código PHP:
<head>
<title>urldecode($_GET['titulo'])</title>
</head>
Un saludo,