Hola,
Bueno, creo que me debes un par de copas.
Lo que usa tu sistema es la codificacion UTF-8. En PHP la puedes manejar con las funciones utf8_encode() y utf8_decode() (
http://es2.php.net/manual/es/function.utf8-encode.php). Y mira este codigo que he probado:
Código PHP:
<?php
echo urlencode(utf8_encode("Á"));
?>
La salida que muestra es %C3%81 , justo lo que estabas haciendo con tu ereg_replace(). Es decir, primero pasa la cadena a UTF-8 y luego la urlencodeas para pasarla como paramentro.
Espero haberte sido de ayuda.