Hola de nuevo.
  Problema identificado:
 El Script.aculo.us (y prácticamente todo lo que tenga que ver con AJAX) funciona con UTF-8, pero en mi base de datos MySQL el texto se almacena como Latin 1 (ISO 8891-1) de manera predeterminada.
Entonces, el dato es pasado del Ajax.Autocompleter() como UTF-8 y por eso las incongruencias. 
Solución al problema descrito arriba:
 - Usar la función de PHP utf8_decode para convertir el dato recibido por el método $_POST['parametro'] en Latin 1.
  - Usar la función inversa utf8_encode para convertir el dato devuelto a UTF-8, y así evitar problemas con caracteres raros en el Output.
- En lugar del punto 2 (ojo es en lugar de, no además de), se puede añadir un header("Content-Type: text/html; charset=iso-8859-1"); al principio del Script PHP.
  
  
El código XHTML+javascript:
Nota: en el HEAD del documento se deben importar los archivos prototype.js y scriptaculous.js 
como se describe aquí.  Código HTML:
 <input type="text" name="pais_clg" id="pais_clg" value="<?php echo $rs['dato']; ?>" size="32"/>
<span id="indicator1" style="display: none">Procesando...</span>
<div id="output1" class="autorelleno"></div>
<script type="text/javascript" language="javascript">
<!--
new Ajax.Autocompleter(
            "pais_clg",
            "output1",
            "scriptQueDevuelveElValor.php",
            {
                method: "post",
                paramName: "value",
                minChars: 2,
                indicator: 'indicator1',
            });
-->
</script>  El código PHP scriptQueDevuelveElValor.php 
 Código PHP:
    <?php
require_once("conecta.php");
mysql_select_db($database, $conexion);
$sql = "
        SELECT valor 
        FROM tabla 
        WHERE valor 
        LIKE '%".utf8_decode($_POST['value'])."%' 
        GROUP BY valor";
$rs = mysql_query($sql, $conexion);
echo "<ul>";
while($data = mysql_fetch_assoc($rs)) { 
    echo "<li>".stripslashes(utf8_encode($data['valor']))."</li>";
}
echo "</ul>";
?>    
  O bien... 
 Código PHP:
    <?php
header("Content-Type: text/html; charset=iso-8859-1");
require_once("conecta.php");
mysql_select_db($database, $conexion);
$sql = "
        SELECT valor 
        FROM tabla 
        WHERE valor 
        LIKE '%".utf8_decode($_POST['value'])."%' 
        GROUP BY valor";
$rs = mysql_query($sql, $conexion);
echo "<ul>";
while($data = mysql_fetch_assoc($rs)) { 
    echo "<li>".stripslashes($data['valor'])."</li>";
}
echo "</ul>";
?>    
  Saludos y espero que les sea útil... pasé mis últimas 4 horas tratando de resolverlo