algo estás haciendo mal. el evento correcto es onkeyup.
aquí tienes un ejemplo de ello. la parte del servidor está en asp y php (algo anticuado pero aún válido)
edito.-
según la respuesta que te dí entendí que no funciona con el shortcut (ctlr + v). la solución pasa por usar el evento onpaste. este evento ocurre antes que el el valor del control sea cambiado, por lo que tendrás que usar un temporizador
Cita: elemento.addEventListener('paste', fuction() {pegar(this.value)}, false);
function pegar(val) {
setTimeout(function() {autocomplete(val)}, 0);
}