No se cuantos sean los registros que vas a mostrar, pero yo con poco más de 3000 lo tuve que eliminar. Si tuviera más tiempo le seguiría con Ajax por que la prueba de que se puede, como mencioné antes, es google suggest (
http://www.google.com/webhp?complete=1&hl=en), pero entre que no tengo tiempo y entre que el ac.js esta bastante enredado, pues no le he atinado.
De todas forma suerte en tus desarrollos biffly