Seleción de listas largas

[Subotai]

Buenas a todos,

Tengo el siguiente problema, en una página php el usuario tiene que elegir un valor de dos listas bastante largas, uno de cada uno, pero no siempre tendrá que hacerlo.

Utilizando php+html tradicional se montan dos listas de unos 8000 registros cada una aproximadamente, como os imaginaréis resulta muy lenta la carga por lo que una posible solución sería que esas listas se generasen únicamente cuando fuera necesario, llamándolas desde un enlace o un botón por ejemplo.

También hay que tener en cuenta que como son listas larguísimas no puedo utilizar un autocomplete o autosuggest porque no son funcionales (ya lo he intentado y no soportan tantos registros)

Bien, por donde tiro? Debería usar alguna librería tipo Mootools o Jquery?
Hasta ahora todo lo que he echo en este ámbito ha sido haciendo pequeños cambios a este tipo de librerías, pero mis conocimientos son un poco limitados en estas tecnologías.

Gracias a todos :)