enlaces sencillos con php

[machbel]

Queria que mi web usara enlaces sencillos pero sin usar el mod rewrite de apache, ya que no puedo ponerlo, pero me valen enlaces como los de wikipedia http://es.wikipedia.org

En cuanto a tratar la url y demas no tengo problema, pero al poner alguna tilde, ñ u otro signo de puntuacion empiezan los problemas, ya que si pongo esta url:
/index.php/áéíóúaeiouñn

con $_SERVER['REQUEST_URI'] obtengo:
en mozilla: /index.php/%E1%E9%ED%F3%FAaeiou%F1n
en explorer: /index.php/%C3%A1%C3%A9%C3%AD%C3%B3%C3%BAaeiou%C3%B1n

y con $_SERVER['PHP_SELF']
en mozilla: /index.php/áéíóúaeiouñn
en explorer: /index.php/áéÃ*óúaeiouñn

me resulta extraño que pase eso, pero tiene que haber alguna forma de arreglarlo sin distinguir el navegador, y reemplazando la menor cantidad posible de caracteres, ya que no es plan de andar comprobando si hay %C3%A1 y similares en todos los enlaces.

[Cluster]

Prueba con urldecode() y/o con utf8_decode()

http://www.php.net/manual/en/function.urldecode.php
http://www.php.net/manual/en/function.utf8-decode.php

Un saludo,